问题描述:把一个偶数拆成两个不同素数的和,有几种拆法呢?
输入:输入包含一些正的偶数,其值不会超过10000,个数不会超过500,若遇0,则结束。
输出:对应每个偶数,输出其拆成不同素数的个数,每个结果占一行。
样本输入:30
26
0
样本输出:3
2
思路:
将输入的数用循环分为每一组加起来能够与原数相等的两个数(比如输入30,则可以分为1+29,2+28,……)并判断每一组的两个数是否同时为素数,如果是,则可拆法数(即将输出的值)加一;
这里用sqrt()来找素数比较快(因为一个数由两个数相乘时,两个数中小的那个数肯定小于乘后的数的开方值(eg:30=5*6,5*5<30<6*6;63=7*9;7*7<63<9*9)......... ),这样代码就不会超时(The Time Exceeded)......,如果不用答案也会正确,但会超时。
代码:
#include<stdio.h>
#include<math.h>
int su(int x)
{
int i,j=0;
for(i=2;i<=sqrt(x);i++)
{
if(x%i==0)j++;
}
if(j==0)return 1;
else return 0;
}
main()
{
int a;
while(scanf("%d",&a)!=EOF&&a)
{
int i,m,n,count=0;
for(i=2;i<a/2;i++)
{
m=su(i);
n=su(a-i);
if(m&&n)count++;
}
printf("%d\n",count);
}
}