求所给的数能用多少种连续素数的和表示。
类似于求最大连续和优化的方法。使用前缀和减少运算。然后输入范围是2到10000，貌似可以打表交。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include<cstdio>
const int maxn=10010;
int isp[1250],pre_p,sum[1250];
bool np[maxn]={true,true};
void prepare(){
for(int i=2;i<maxn;++i){
if(!np[i])
isp[pre_p++]=i;
for(int j=0;j<pre_p&&i*isp[j]<maxn;++j){
np[i*isp[j]]=true;
if(!(i%isp[j])) break;
}
}
for(int i=1;i<=pre_p;++i)
sum[i]=sum[i-1]+isp[i-1];
return;
}
int main(){
prepare();
int n;
while(~scanf("%d",&n)&&n){
int cnt=0;
for(int i=0;i<pre_p;++i){
if(isp[i]>n) break;
for(int j=i+1;j<=pre_p;++j)
if(n==sum[j]-sum[i]) ++cnt;
}
printf("%d\n",cnt);
}
return 0;
}
|
** 本文迁移自我的CSDN博客，格式可能有所偏差。 **