問題
ゴールドバッハ予想とは、「2 より大きいすべての偶数は 2 つの素数の和で表せる」という予想です。まだ証明されていませんが、この問題で扱う範囲よりはるかに大きな数まで正しいことが確かめられています。表し方が複数あることもよくあります(28 = 5 + 23 = 11 + 17)。その中から、小さい方の素数ができるだけ小さくなるものを求めてください。
goldbach_partition(n) を実装してください。
p = 2, 3, 5, ... と順に試して n − p が素数かどうかを調べれば、すぐに答えが見つかります。小さな p でほとんどの場合うまくいくからです。10^9 までの数を試し割りで素数判定するには、約 31,623 までの約数を調べるだけで済みます。
入力
n: 2 より大きい偶数。
出力
p と q が素数で、p + q = n、p ≤ q を満たし、さらに p がこれを満たす最小の素数であるような [p, q] を返してください。
制約
4 ≤ n ≤ 10^9、n は偶数
例
入力:
n = 28
期待される出力:
expected = [5, 23]
入力:
long long n = 28;
期待される出力:
std::vector<long long> expected = {5, 23};
入力:
long n = 28;
期待される出力:
long[] expected = new long[] {5, 23};
解説
28 − 2 = 26 と 28 − 3 = 25 は素数ではありませんが、28 − 5 = 23 は素数なので、答えは [5, 23] です。
入力:
n = 4
期待される出力:
expected = [2, 2]
入力:
long long n = 4;
期待される出力:
std::vector<long long> expected = {2, 2};
入力:
long n = 4;
期待される出力:
long[] expected = new long[] {2, 2};
解説
2 + 2 しかないので、答えは [2, 2] です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
p = 2, 3, 4, ... と試していき、p と n − p がどちらも素数になった最初の p で止めます。
ヒント 2
素数判定では、平方根までの約数を試せば十分です。
ヒント 3
最小の p で止めるので、p ≤ n − p は自動的に満たされます。
目安の計算量
時間 O(k √n)(k は試した候補の数)、追加メモリ O(1)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。