Sum of Consecutive Prime Numbers POJ - 2739 线性欧拉筛（线性欧拉筛证明）

题意：给一个数 可以写出多少种  连续素数的合

思路：直接线性筛 筛素数 暴力找就行   (素数到n/2就可以停下了,优化一个常数)

其中：线性筛的证明参考：https://blog.csdn.net/nk_test/article/details/46242401

　　　　　　　　　　　　https://blog.csdn.net/qq_40873884/article/details/79124552

　　　　　　　　　　　　https://blog.csdn.net/baoli1008/article/details/50788512

线性筛的思想 就是 每个数都有一个最小的质因素  外层i是质因数个数 内层j是primes[i]的标号  用每个质因数筛 每个数只要被筛一遍

　　　　　　同时， if(i%primes[j]==0 )break; 这里指的是如果i%primes[j]==0了 那么i就有因数 primes[j] 所以i*prime[j+1]肯定已经被筛掉了

因为是从小到大开始筛的，i中还有primes[j] 说明 i*primes[j+1]最小的质因数等于primes[j]  所以肯定会被筛掉 只是可能循环轮次

　　　　　　不同，可能是下一个i或者其他i

 #include<cstdio>

 #include<cstring>

 using namespace std;

 bool Is_Primes[];

 int Primes[];

 int cnt;

 void Prime(int n){

      cnt=;

      memset(Is_Primes,,sizeof(Is_Primes));

     for(int i=;i<=n;i++){

         if(!Is_Primes[i])

             Primes[cnt++]=i;

         for(int j=;j<cnt&&i*Primes[j]<n;j++){

             Is_Primes[Primes[j]*i]=;

             if(i%Primes[j]==)break;

         }

     }

 }

 int main(){

     int n;

     Prime();

     while(scanf("%d",&n)==&&n){

         int ans=;

         for(int i=;i<cnt&&Primes[i]<=n;i++){

             int temp=i;

             int sum=;

             while(sum<n&&temp<cnt){

                 sum+=Primes[temp++];

             }

             if(sum==n)ans++;

         }

         int flag=;

         printf("%d\n",ans);

     }

     return ;

 }