#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#define max 10001
#define sum 1230//10000以下总共有1229个素数
using namespace std;
int prime [sum];//这个数组用于存放素数

int num(int n)//用于计算可能的组合的个数。
{
    int a=prime[1],ans=0;//ans为个数，a为当前计算的和，n为目标值
    for(int i=1,j=2;j<sum&&prime[i]<=n&&i<=j;i++)
    {
        a-=prime[i-1];
        while(a<n&&j<sum)
        {
            a+=prime[j++];
        }
        if(a==n){ans++;}
    }
    return ans;
}


int main()
{
    bool * data=new bool [max];//双下标法找素数
    memset(data,true,max*sizeof(bool));
    data[0]=false;data[1]=false;prime[0]=0;
    for(int i=2,j=1,k;i<max;i++)
    {
        if(!data[i]){continue;}
        prime[j++]=i;//记录素数
        for(k=(i<<1);k<max;k+=i){data[k]=false;}
    }
    delete(data);//不用了就释放内存
    int n;
    while(cin>>n)
    {
        if(!n){break;}
        cout<<num(n)<<endl;
    }
    return 0;
}

• Re:过了贴代码攒rp，有注释有真相 (1028) 504512803 2012-02-04 15:45:39