Sum of Consecutive Prime Numbers
2007.08.24 22:20 ACM/ICPC 2005
[問題] ACM/ICPC Asia Regional 2005 Tokyo: Problem A
[解説]
エラトステネスの篩+2重ループ。
[サンプルプログラム]
[解説]
エラトステネスの篩+2重ループ。
[サンプルプログラム]
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 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |