問題
双子素数とは、11 と 13、17 と 19 のように、差が 2 である 2 つの素数の組のことです。大きい方の数が limit 以下になる組をすべて求めてください。
twin_primes(limit) を実装してください。
上限が大きい場合は、1 つずつ素数判定するのではなく、ふるいを使ってすべての素数をまとめて求めましょう。
入力
limit: 組の大きい方の素数がとりうる最大値。
出力
2 つの数がどちらも素数で、p + 2 ≤ limit を満たす組 [p, p + 2] のリストを、p の昇順に並べて返してください。1 組もなければ空のリストを返してください。
制約
0 ≤ limit ≤ 10^6
例
入力:
limit = 20
期待される出力:
expected = [
[3, 5],
[5, 7],
[11, 13],
[17, 19]
]
入力:
long long limit = 20;
期待される出力:
std::vector<std::vector<long long>> expected = {
{3, 5},
{5, 7},
{11, 13},
{17, 19}
};
入力:
long limit = 20;
期待される出力:
long[][] expected = new long[][] {
new long[] {3, 5},
new long[] {5, 7},
new long[] {11, 13},
new long[] {17, 19}
};
解説
20 以下の素数は 2, 3, 5, 7, 11, 13, 17, 19 で、差が 2 のものを組にすると [[3, 5], [5, 7], [11, 13], [17, 19]] になります。
入力:
limit = 6
期待される出力:
expected = [
[3, 5]
]
入力:
long long limit = 6;
期待される出力:
std::vector<std::vector<long long>> expected = {
{3, 5}
};
入力:
long limit = 6;
期待される出力:
long[][] expected = new long[][] {
new long[] {3, 5}
};
解説
3 と 5 はどちらも素数で 5 ≤ 6 ですが、7 は上限を超えるので、[[3, 5]] だけです。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
ふるいを使えば、1 つずつ判定するよりはるかに速く、10^6 までの素数がすべて求まります。
ヒント 2
そのあと、p + 2 ≤ limit を満たすすべての p を調べます。
ヒント 3
最初の組は (3, 5) なので、limit が 5 未満なら空のリストになります。
目安の計算量
時間 O(limit log log limit)、追加メモリ O(limit)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。