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