POJ 2739 Sum of Consecutive Prime Numbers(素數)

POJ 2739 Sum of Consecutive Prime Numbers(素數)

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