这题必然的筛选法,出现了2个问题:1.开始开了一个 result 数组(全局变量),想把素数挨个存进来,虽然还计数估算了的,一直的runtime error , 后来发现是多此一举,去掉之后就变成wrong answer,看来可以编译了。这么说来,一百万对于两个大数组还是有点吃不消的 2.筛的时候一定要筛完整,for(j=2*i;j<MAXN;j+=i)prime[j]=1;这里开始用的
j<(MAXN/i),明显就错了。
另外我很好奇题目中说的"Goldbach's conjecture is wrong.",很明显不会wrong的,wrong了科学家们还继续证明干嘛,可是我AC以后看网上的结题报告居然还真有把wrong考虑进去的人。。。
2个错误都存在的代码
#include <stdio.h> #define MAXN 1000002 #define PrimeNum 671000 int prime[MAXN]; //用筛法求素数,1代表不是素数(被筛掉) int result[PrimeNum]; int main() { //先打出素数表 prime[0]=prime[1]=1; //开始去掉prime[0]和prime[1] int i,j; for(i=2;i<MAXN;i++) { if(prime[i]==0) //如果prime[i]是素数就把他的倍数都筛掉 { for(j=2*i;j<(MAXN/i);j+=i) prime[j]=1; } } //test 1 /*int count=0; for(i=2;i<MAXN;i++) if(prime[i]==0) count++; printf("一百万以内的素数有 %d 个\n",count);*/ //test 2 /*for(i=2;i<100;i++) if(prime[i]==0) printf("%d ",i);*/ int count=0; for(i=3;i<100;i++) if(prime[i]==0) { result[count]=i; count++; } /*for(i=0;i<100;i++) printf("%d ",result[i]);*/ int n; while(scanf("%d",&n)) { if(n==0) break; for(i=0; ;i++) if(prime[n-result[i]]==0) { printf("%d = %d + %d\n",n,result[i],n-result[i]); break; } } return 0; }
正确的代码
#include <stdio.h> #define MAXN 1000002 int prime[MAXN]; //用筛法求素数,1代表不是素数(被筛掉) int main() { //先打出素数表 prime[0]=prime[1]=1; //开始去掉prime[0]和prime[1] int i,j; for(i=2;i<MAXN;i++) { if(prime[i]==0) //如果prime[i]是素数就把他的倍数都筛掉 { for(j=2*i;j<MAXN;j+=i) prime[j]=1; } } int n; while(scanf("%d",&n)) { if(n==0) break; for(i=3; ;i++) if(prime[i]==0 && prime[n-i]==0) { printf("%d = %d + %d\n",n,i,n-i); break; } } return 0; }
时间: 2024-12-24 00:47:51