MPRIME1 - Sum of Primes
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<cstring>
#define N 11000
int pr[N], f[N], cnt;
bool prime[N];
void eratos() {
memset(prime, -1, sizeof prime);
for(int i = 2; i * i <= N; ++i) if(prime[i])
for(int j = i+i; j <= N; j += i) prime[j] = 0;
for(int i = 2; i <= N; ++i) if(prime[i]) pr[cnt++] = i;
}
void calc() {
for(int i = 0; i < cnt; ++i)
for(int j = i, sum = pr[i]; j < cnt && sum <= N; sum += pr[++j])
++f[sum];
}
int main() {
eratos();
calc();
for(int n; scanf("%d", &n) != EOF && n != 0; printf("%d\n", f[n]));
return 0;
}