809
技術社區[雲棲]
poj 2262 Goldbach's Conjecture 【素數篩】
這題必然的篩選法，出現了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;
}
最後更新：2017-04-03 15:22:13