题意：
给出n，求把n写成若干个连续素数之和的方案数。
分析：
这道题非常类似大白书P48的例21，上面详细讲了如何从一个O(n3)的算法优化到O(n2)再到O(nlogn)，最后到O(n)的神一般的优化。
首先筛出10000以内的素数，放到一个数组中，然后求出素数的前缀和B。这样第i个素数一直累加到第j个素数，就可表示为Bj - Bi-1
枚举连续子序列的右端点j，我们要找到Bj - Bi-1 = n，也就是找到Bi-1 = Bj - n。
因为Bj是递增的，所以Bi-1也是递增的，所以我们就不用从头枚举i，而是接着上一次循环i的值继续枚举。
还有就是，因为本身素数也是递增的(废话!)，所以j也不一定要枚举到最后一个素数，只要在不超过n的素数里枚举就行了。
说了这么多，我就是想说人家算法的效率已经很高了，15ms，UVa上居然排300+名，鄙视那些打表狗。
#include <cstdio>
#include <cmath> const int maxn = ;
const int maxp = ;
bool vis[maxn + ];
int prime[maxp], sum[maxp], cnt = ; void Init()
{
int m = sqrt(maxn + 0.5);
for(int i = ; i <= m; ++i) if(!vis[i])
for(int j = i * i; j <= maxn; j += i) vis[j] = true;
for(int i = ; i <= maxn; ++i) if(!vis[i]) prime[cnt++] = i;
cnt--;
//求素数的前缀和
for(int i = ; i <= cnt; ++i) sum[i] = sum[i - ] + prime[i];
} int main()
{
Init();
int n;
while(scanf("%d", &n) == && n)
{
int i = , ans = ;
for(int j = ;j <= cnt && prime[j] <= n; ++j)
{
int temp = sum[j] - n;
while(sum[i] < temp) ++i;
if(sum[i] == temp) ans++;
}
printf("%d\n", ans);
} return ;
}
代码君