首页 > 代码库 > 【素数】 poj 2739 一个数能有多少种连续素数相加方案

【素数】 poj 2739 一个数能有多少种连续素数相加方案

简单题 素数打表   根据数据量  用n2算法遍历  开一个save【k】素数存前k个素数和即可。

 

#include <iostream>#include <cstdio>#include <memory.h>#include <cmath>using namespace std;const int maxn=10002;int pri[maxn+1];int save[2000+1];int s[2000+1];void make_pri(){    pri[0]=0;    pri[1]=0;    for(int i=2;i<=maxn;i++)    {        pri[i]=1;    }    for(int i=2;i*i<=maxn;i++)    {        if(pri[i])        {            for(int j=i*i;j<=maxn;j+=i)            pri[j]=0;        }    }}void init(){    memset(save,0,sizeof(save));    memset(s,0,sizeof(s));    int i,j=2;    s[1]=2;    for(i=3;i<=maxn;i++)    {        if(pri[i]==1)        {            s[j++]=i;        }    }    for(int i=1;i<=2000;i++)    {        save[i]=save[i-1]+s[i];    } }int main(){    //freopen("in.txt","r",stdin);    memset(save,0,sizeof(save));    make_pri();    init();    int n;    while(cin >> n && n!=0)    {        int cnt=0;        int last;        if(pri[n]==1)        {            for(int i=2000;i>=1;i--)            {                if(s[i]==n)                {                    last=i;                }            }        }        else        {            for(int i=2000;i>=1;i--)            {                if(s[i]<n && s[i+1]>n)                {                    last=i;                }            }        }        for(int i=last;i>=1;i--)        {            for(int j=i-1;j>=0;j--)            {                if(save[i]-save[j]==n)                {                    cnt++;                }            }        }        cout << cnt << endl;    }    return 0;}

 

【素数】 poj 2739 一个数能有多少种连续素数相加方案