Monday, December 17, 2007

Sum of Consecutive Prime Numbers

ACCEPTED !!! An Opener again from Tokyo 2005/06
____________________________________________________________________
Question: Sum of Consecutive Prime Numbers
____________________________________________________________________

int isprime[10001], ind[10001], primes[10001];

int isPrime(int n) {
int s = (int)sqrt(n);
for(int i = 2; i <= s; i++) if(n % i == 0) return 0;
return 1;
}

int main() {

int pcount = 0;
for(int i = 2; i <= 10000; i++) {
isprime[i] = 0;
if(isPrime(i)) {
isprime[i] = 1;
primes[pcount] = i;
ind[i] = pcount;
pcount++;
}
}

while(1) {

int n;
cin >> n;
if(n == 0) break;

int p = n;
while(!isprime[p]) p--;

int start = ind[p];
int sum = 0, c = 0;
int i = start;

while(i >= 0) {
while(n > sum) {
sum += primes[i];
i--;
}
if(sum == n) c++;
sum -= primes[start];
start--;
}

cout << c << endl;
}

}
____________________________________________________________________

No comments:

Contributors