杭电1397

杭电1397

                哥德巴赫猜想的

问题描述
任何偶数哥德巴赫猜想:n大于等于4,存在至少一对素数p1和p2,n = p1+p2。
这个猜想尚未证明也不拒绝。没人知道是否这个猜想成立。然而,人们可以发现这样一双质数,如果有的话,对于给定的一个偶数。这里的问题是编写一个程序,报告所有成对的质数的数量满足条件给定的一个偶数的猜想。

给出一个偶数序列作为输入。对应于每个数字,程序应该输出对上面提到的数量。注意,我们感兴趣的数量对本质上是不同的,因此你不应计数(p1,p2)和(p1,p2)分别作为两个不同的配对。

输入
在每个输入行给出一个整数。你可能认为每个整数都是偶数,大于或等于4,小于2 ^ 15。输入结束后由数字表示0。

输出
每个输出行应该包含一个整数。没有其他字符应该出现在输出。

样例输入
6
10
12
0

样例输出
1
2
1

错误代码:

# include <iostream>
# include <cstdio>
# include <cmath>using namespace std;int f(int n){if(n<=1) return 0;int len = sqrt(n);for(int i=2;i<=len;i++)if(n%i==0) return 0;return 1;
}int a[10000];
int main(){int  i,j,k;int n,m;j = 0;for(i=2;i<=65535;i++){if(f(i)){a[j++] = i;printf("%dn",a[j-1]);}}while(scanf("%d",&n),n!=0){int cnt = 0;for(i=0;a[i]<=n/2;i++){int t = n - a[i];if(f(t)){ //每次又调用,引起超时  时间复杂度过大cnt++;}}printf("%dn",cnt);}return 0;
}

修改代码:

# include <iostream>
# include <cstdio>
# include <cmath>
# include <cstring>
using namespace std;int f(int n){if(n<=1) return 0;int len = sqrt(n);for(int i=2;i<=len;i++)if(n%i==0) return 0;return 1;
}int a[700000];
int main(){int  i,j,k;int n,m;memset(a,0,sizeof(a));j = 0;for(i=2;i<=65535;i++){if(f(i)){a[i] = i;//printf("%dn",a[j-1]);}}while(scanf("%d",&n),n!=0){int cnt = 0;for(i=0;a[i]<=n/2;i++){int t = n - a[i];if(a[t]){ //利用下标cnt++;}}printf("%dn",cnt);}return 0;
}