Sum of Consecutive Prime Numbers

[問題] ACM/ICPC Asia Regional 2005 Tokyo: Problem A

[解説]

エラトステネスの篩＋２重ループ。

[サンプルプログラム]

001 #include<iostream>
002 #include<cmath>
003 using namespace std;
004 #define MAX 10000
005 #define PMAX 1229
006 bool prime[MAX+1]; // prime number table

007 int T[MAX+1];
008 
009 void eratos(int n){
010     fill(prime, prime+MAX, false);
011     for ( int i = 3; i <= n; i += 2 ) prime[i] = true;
012     prime[2] = true;
013     for ( int i = 3; i*i <= n; i += 2 ) {
014         if ( !prime[i] ) continue;
015         for ( int j = i * i, k = i * 2; j <= n; j += k ) prime[j] = false;
016     }
017 }
018 
019 void initialize(){
020     eratos(MAX);
021     int plist[1229];
022     int size = 0;
023     for ( int i = 2; i <= MAX; i++ ){
024         if  ( prime[i] ) plist[size++] = i;
025     }
026     for ( int i = 0; i <= MAX; i++ ) T[i] = 0;
027     
028     for ( int i = 0; i < size; i++ ){
029         int sum = 0;
030         for ( int j = i; j < size; j++ ){
031             sum += plist[j];
032             if ( sum >= MAX ) continue;
033             T[sum]++;
034         }
035     }
036 }
037 
038 main(){
039     initialize();
040     int n;
041     while(1){
042         cin >> n;
043         if ( n == 0 ) break;
044         cout << T[n] << endl;
045     }
046 }