首页 > 代码库 > 【素数】 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 一个数能有多少种连续素数相加方案
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。