poj 2262 Goldbach's Conjecture 2007/09/15

2262 -- Goldbach's Conjecture

ゴールドバッハの予想 - Wikipedia

解き方がすぐにおもいつかなかったので、discussをチラ見して、すぐにコードを書いて、submitしたのですが、時間切れでacceptされず。

何度もためしてもだめ。

それで、C++のコードをみつけてコピーして試したら、あっさり、acceptされたので、悩みました。

isPrimeというメソッドを作成して素数判定していたのですが、やはりそれが遅かったです。

はじめの実装は、

static boolean isPrime_1(int p) {
return BigInteger.valueOf(p).isProbablePrime(10);
}

でした。

ちなみにjavadocの説明は、

この BigInteger が素数である可能性が高い場合は true を返し、必ず合成数である場合は false を返します。certainty が 0 以下である場合、true を返します。

パラメータ:
certainty - 呼び出し側が許容しない確率の尺度。この BigInteger が素数である確率が (1 - 1/2certainty) を超える場合は true を返す。実行時間はこのパラメータの値に比例する
戻り値:
この BigInteger が素数である可能性が高い場合は true、必ず合成数である場合は false

次に、これを変更したら時間超過で失敗せずにacceptされました。

変更後の実装は、

static boolean isPrime(int n) {
int i;
for (i = 2; i <= Math.sqrt(n); i++)
if (n % i == 0)
return false;
return true;
}