POJ 2739 Sum of Consecutive Prime Numbers(素数)

http://poj.org/problem?

id=2739

题意：

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

分析：

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

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

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

因为10000以内的素数非常少（仅仅有1000多个），所以本题找连续素数和能够暴力枚举解决。

AC代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

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\n");

            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<bound;i++)

        {

            int sum=0;

            for(int j=i;j<bound;j++)

            {

                sum += prime[j];

                if(sum==x)

                {

                    ans++;

                    break;

                }

            }

        }

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

    }

    return 0;

}