POJ 2739 Sum of Consecutive Prime Numbers

問題

2以上10000以下の整数nが与えられる。nを連続する素数の和で表したい。何通りの方法があるか求めよ。素数一つで表せる場合も該当する。

やりかた

エラトステネスの篩をして10000以下の素数の数列を求めておき、それらの部分数列の和を全列挙して該当するものの数を数えればいい。予め素数列の和を前計算しておく必要がある。

以下ソース。

bool sieve[10100];

int main(int argc, char **argv){
  FILL(sieve, true);
  sieve[0] = sieve[1] = false;
  for(int i = 2; i <= 10000; i++)
    for(int j = 2 * i; j <= 10000; j += i)
      sieve[j] = false;

  vector<int> p;
  p.push_back(0);//まず0を入れておくと楽
  for(int i = 0; i <= 10000; i++)
    if(sieve[i]) p.push_back(i);
  for(int i = 1; i < p.size(); i++)//素数列の和を前計算
    p[i] += p[i - 1];
  
  int n;
  while(cin >> n, n){
    int cnt = 0;
    for(int i = 0; i < p.size(); i++)
      for(int j = 0; j < i; j++)
	if(p[i] - p[j] == n) cnt++;
    cout << cnt << endl;
  }
}

最初しゃくとりかなと思ったけど10000以下の素数はせいぜい1300個程度なので単純計算で行ける。