POJ2739 Sum of Consecutive Prime Numbers

心已赠人 2022-07-11 12:08 259阅读 0赞

题目大意：给出一个数n，判断n是否可以被连续质数的和表示，可以的话，输出可能的情况总数。输入以0结束。

  1. #include <iostream>
  2. using namespace std;
  3. #define max_n 10010
  4. int prime[max_n];
  5. int pcnt;
  6. bool notprime[max_n];
  8. void initprime(int n)
  9. {
  10.     pcnt=0;
  11.     for(int i=2;i<=n;i++)
  12.     {
  13.         if(!notprime[i])
  14.         {
  15.             prime[pcnt++]=i;
  16.             for(int j=i+i;j<=n;j+=i)
  17.                 notprime[j]=true;
  18.         }
  19.     }
  20. }
  22. int n;
  23. int cnt;
  25. int main()
  26. {
  27.     initprime(10000);
  29.     while(scanf("%d",&n),n)
  30.     {
  31.         cnt=0;
  32.         for(int i=0;i<pcnt;i++)
  33.         {
  34.             int sum=0;
  35.             for(int j=i;j<pcnt&&sum<n;j++  )//sum=n,就会多循环一次
  36.             {
  37.                 sum+=prime[j];
  38.             }
  39.             if(sum==n) cnt++;
  40.         }
  42.         printf("%d\n",cnt);
  43.     }
  44.     return 0;
  45. }

艾氏筛选法

发表评论

表情：
评论列表 （有 0 条评论，259人围观）

还没有评论，来说两句吧...

相关阅读