POJ 2262 Goldbach's Conjecture

問題

http://poj.org/problem?id=2262

４以上の偶数は２つの奇素数の和で表せるという予想をゴールドバッハ予想という。入力nに対しそのような２つの奇素数を返せ。複数ある場合は絶対値の差が最大になるペアを返せ。

やりかた

エラトステネスの篩をしたあと、探索する。O(n loglog(n))

以下ソース。

bool sieve[1000001];

int main(){
  int n;
  memset(sieve, true, sizeof(sieve));
  sieve[0] = sieve[1] = false;
  for(int i = 2; i <= 1000000; i++) if(sieve[i])
    for(int j = 2 * i; j <= 1000000; j += i)
      sieve[j] = false;
  while(cin >> n, n){
    for(int i = 3; i <= n - i; i += 2)
      if(sieve[i] && sieve[n - i]){
	cout << n << " = " << i << " + " << n - i << endl;
	break;
      }
  }
  return 0;
}