I haven't programming for years, so I decided to refresh it today. At least, this is the key point of CS&T, right?
This problem is quite easy. It is easy to see that 2739 belongs to Number Theory. And key point lies on "consecutive"(If not, it'll be much harder:|). Since it requires that, and we only need to use the primes in [2,10000], it is easy to see that we can solve this in the following steps:
1.Get all primes in [2,10000];
2.Reset the counter to 0. Then, start from 2 and calculate the sums, namely, 2, 2+3, 2+3+5, ..., until the sum is great than 10000; for those who are less than that, increase the counter of that sum, correspondingly, 2,5,10,......
3.For each input between 2 and 10000, output the precalculated sum.
Source code as followed:
#include <iostream>
#include <cmath>
using namespace std;
const int MAXN = 10000;
bool f[MAXN+10];
int np;
int p[MAXN+10];
int sum[MAXN+10];
void findPrime() {
memset(f, 1, sizeof(f));
f[0] = 0; f[1] = 0;//doesn't matter anyway
int tmp = abs(sqrt(MAXN*1.0));
for (int i = 2; i <= tmp; i++) {
if (f[i]) {
for (int j = i+i; j <= MAXN; j+=i)
f[j] = 0; //false
}
}
int ctr = 0;
for (int i = 2; i <= MAXN; i++)
if (f[i]) {
p[ctr++] = i;
}
np = ctr;
}
void geneSum() {
memset(sum, 0, sizeof(sum));
for (int i = 0; i < np; i++) {
int tsum = 0;
for (int j = i; j < np; j++) {
tsum += p[j];
if (tsum > MAXN) break;
sum[tsum]++;
}
}
}
void initi() {
findPrime();
geneSum();
}
int main() {
initi();
int n;
while (1) {
scanf("%d", &n);
if (n == 0) break;
printf("%d\n", sum[n]);
}
return 0;
}