POJ.2739 Sum of Consecutive Prime Numbers(水)

代码总览

#include <cstdio>

#include <cstring>

#include <vector>

#include <cmath>

#define nmax 10005

using namespace std;

int prime[nmax],n;

vector<int> vprime;

void init()

{

    memset(prime,0,sizeof(prime));

    int up = sqrt(nmax)+1;

    for(int i = 2;i<=up;++i){

        if(prime[i] == 0)

            for(int j = 2;i*j<=nmax;++j){

                prime[i*j] = 1;//not prime

            }

    }

    for(int i = 2; i<=nmax;++i){

        if(prime[i] == 0){

            //printf("%d\n",i);

            vprime.push_back(i);

        }

    }

}

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    init();

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

        int ans = 0;

        int total = 0;

        for(int i = 0;i<vprime.size();++i){

            total = vprime[i];

            if(vprime[i] == n){

                ans++;

                break;

            }else if(vprime[i]>n) break;

            for(int k = i+1;k<vprime.size();++k){

                total += vprime[k];

                if(total == n) ans++;

                else if(total>n) break;

            }

        }

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

    }

    return 0;

}