https://vjudge.net/problem/UVA-1210
题意:
输入整数n,有多少种方案可以把n写成若干个连续素数之和?
思路:
先素数打表,然后求个前缀和。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll; const int maxn=+; int n; int primes[maxn];
ll sum[maxn];
int vis[maxn];
int cnt; void get_prime()
{
cnt=;
int m = sqrt(maxn + 0.5);
memset(vis, , sizeof(vis));
for (int i = ; i < m;i++)
{
if(!vis[i])
{
for(int j=i*i;j<maxn;j+=i)
vis[j]=;
}
}
sum[]=;
for(int i=;i<=maxn;i++)
{
if(!vis[i])
{
primes[++cnt]=i;
sum[cnt]=sum[cnt-]+i;
}
}
} int main()
{
//freopen("D:\\input.txt", "r", stdin);
get_prime();
while(cin>>n && n)
{
int ans=;
for(int i=;i<=cnt;i++)
for(int j=;j<i;j++)
if(sum[i]-sum[j]==n) ans++;
cout<<ans<<endl;
}
return ;
}