523
poj 2739 Sum of Consecutive Prime Numbers【素數篩】
我覺得這題的數據應該有些刁鑽，一共至少提交了五次，一直是WA，無語了。。。。。。用一個result數組存素數硬是不對。後來就算了，改用直接判斷（法二），繼續WA，後來發現是MAXN至少應為10002（被數據坑了），終於A掉了。。。。。。
後來繼續改法一多次，任然WA，一直不清楚原因。
繼續思考發現有一個很隱蔽的問題就是我後來用到 if(result[i]>n) break; 而result數組中 10000以內 最後一個素數是 9997，後麵全是0了。這樣無法停止，所以必須加一個大數作為哨兵。後來一試，果然AC了！
法二：（AC的代碼）
#include <stdio.h>
#define MAXN 10002
int prime[MAXN]; //用篩法求素數，0代表素數
int main()
{
//先打出素數表
prime[0]=prime[1]=1; //開始去掉[0]和[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,sum,count;
while(scanf("%d",&n))
{
if(n==0)
break;
count=0; //count做最後輸出的 所有表示個數
for(i=0; ;i++) // i 控製素數串第一個數
{
if(prime[i]!=0)
continue;
if(i>n)
break;
sum=0; //sum存 連續素數和
for(j=i; ;j++)
{
if(prime[j]!=0)
continue;
if(sum>n)
break;
sum=sum+j;
if(sum==n)
{
count++;
break;
}
}
}
printf("%d\n",count);
}
return 0;
}
#include <stdio.h>
#define MAXN 10002
int prime[MAXN]; //用篩法求素數，0代表素數
int result[1300];
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 count=0;
for(i=2;i<MAXN;i++)
if(prime[i]==0)
{
result[count]=i;
count++;
}
//test：估算素數個數
/*for(i=0;result[i]!=0;i++)
{
printf("%d ",result[i]);
}
printf("\n1W以內有 %d 個是素數\n",count);*/
int n,sum;
while(scanf("%d",&n))
{
if(n==0)
break;
count=0; //count做最後輸出的 所有表示個數
for(i=0; ;i++)
{
if(result[i]>n)
break;
sum=0; //sum存 連續素數和
for(j=i; ;j++)
{
if(sum>n)
break;
sum=sum+result[j];
if(sum==n)
{
count++;
break;
}
}
}
printf("%d\n",count);
}
return 0;
}
法一（AC的代碼）
#include <stdio.h>
#define MAXN 10002
int prime[MAXN]; //用篩法求素數，0代表素數
int result[1300];
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 count=0;
for(i=2;i<MAXN;i++)
if(prime[i]==0)
{
result[count]=i;
count++;
}
result[count]=99999; //哨兵，因為result最後一個是9997，後麵沒有了
//test：估算素數個數
/*for(i=0;result[i]!=0;i++)
{
printf("%d ",result[i]);
}
printf("\n1W以內有 %d 個是素數\n",count);*/
int n,sum;
while(scanf("%d",&n))
{
if(n==0)
break;
count=0; //count做最後輸出的 所有表示個數
for(i=0; ;i++)
{
if(result[i]>n)
break;
sum=0; //sum存 連續素數和
for(j=i; ;j++)
{
if(sum>n)
break;
sum=sum+result[j];
if(sum==n)
{
count++;
break;
}
}
}
printf("%d\n",count);
}
return 0;
}
最後更新：2017-04-03 14:53:40