POJ 2739 Sum of Consecutive Prime Numbers(素数)

题意：

给你一个10000以内的自然数X，然后问你这个数x有多少种方式能由连续的素数相加得来？

分析：

首先用素数筛选法把10000以内的素数都找出来按从小到大保存到prime数组中。

然后找到数X在prime中的上界，如果存在连续的素数之和==X，那么一定是从一个比X小的素数开始求和（不会超过X的上界），直到和sum的值>=X为止。

所以我们暴力枚举10000以内的所有可能的素数相加和的起始点i，然后求连续素数的和，看看当前以prime[i]开始的连续素数和是否正好==X。

由于10000以内的素数很少（只有1000多个），所以本题找连续素数和可以暴力枚举解决。

AC代码：

#include
  
   
#include
   
     #include
    
      using namespace std; const int maxn=10000; //筛选法求素数 int prime[maxn+5]; int get_prime() { memset(prime,0,sizeof(prime)); for(int i=2;i<=maxn;i++) { if(!prime[i]) prime[++prime[0]]=i; for(int j=1; j<=prime[0] &&prime[j]<=maxn/i; j++) { prime[prime[j]*i]=1; if(i%prime[j]==0) break; } } return prime[0]; } int main() { //预处理：求10000以内所有素数 get_prime(); int x; while(scanf(%d,&x)==1 && x) { if(x<2) { printf(0 ); continue; } int bound=lower_bound(prime+1,prime+prime[0]+1,x)-prime; int ans=0; if(prime[bound]==x) ans++; for(int i=1;i
     
      ?