簡単 0件解決済み 正答率0%

双子素数

上限までの双子素数の組 (p, p + 2) をすべて列挙します。

このチャレンジで学べること

  • ふるいを使って上限までの素数に印を付ける
  • 差が 2 の素数を探して走査する
  • 組が 1 つも入らない小さな上限に対応する

問題

原文(英語)を表示

双子素数とは、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

例

例 1
入力:
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]] になります。

例 2
入力:
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用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。