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;
}

Download