2342.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2342 on 2006-09-12 at 18:56:01 */ 
#include <cstdio>
#include <algorithm>
using namespace std;
 
const int N = 10240;
const int PN = 2048;
 
bool prime[N];
int p[PN], pn = 0;
int sum[N], tot[PN];
 
int main()
{
	int i, j, n;
 
	memset(prime, true, sizeof(prime));
	for(i = 2; i < N; i++) {
		if(!prime[i]) continue;
		p[pn++] = i;
		for(j = 2; i*j < N; j++) prime[i*j] = false;
	}
	memset(sum, 0, sizeof(sum));
	tot[0] = 0;
	for(i = 1; i <= pn; i++) tot[i] = tot[i-1]+p[i-1];
	for(i = 0; i <= pn; i++)
		for(j = i+1; j <= pn; j++)
			if(tot[j]-tot[i] >= N) break;
			else sum[tot[j]-tot[i]]++;
	while(scanf("%d", &n) != EOF && n != 0) printf("%d\n", sum[n]);
 
	return 0;
}