POJ 2909 Goldbach's Conjecture

問題

4以上の整数は2つの素数の和で表せる、という予想をゴールドバッハ予想という。4以上2^15以下の整数nが与えられるので和がnとなるような素数の組数を返せ。ただし(p1,p2)という組と(p2,p1)という組を別々に数えてないけない。

やりかた

エラトステネスの篩をしてから(i,n-i)が該当する組になるかを調べていけばいい。

POJ 2262とほぼ一緒

以下ソース。

bool sieve[1 << 16];

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

  int n;
  while(cin >> n, n){
    int cnt = 0;
    for(int i = 2; i <= n - i; i++)
      cnt += (sieve[i] && sieve[n - i]);
    cout << cnt << endl;
  }
}