中級 0件解決済み 正答率0%

素数を生む二次式

n = 0 から素数が最も長く続く二次式 n² + an + b を求めます。

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

  • 試し割りで素数判定ができる
  • 2つのパラメータの組み合わせを探索できる
  • 同点時の選び方の規則を適用できる

問題

原文(英語)を表示

素数をうまく生み出す二次式があります。たとえば n² + n + 41 は、n = 0 から 39 までのすべてで素数になります。|a| ≤ limit、|b| ≤ limit を満たす整数 a, b について、n = 0, 1, 2, ... と順に調べ、n² + an + b が素数になる値が何個連続するかを数えます(素数でない値が現れたところで止めます)。連続する個数が最も多くなる組を見つけてください。

quadratic_primes(limit) を実装してください。

入力

limit:a と b の絶対値の上限。

出力

[a, b, run] を返してください。run は最長の連続における素数の個数です。同じ個数の組が複数あれば、a が最小のもの、その中でさらに b が最小のものを選びます。2 未満の数は素数ではないので、n = 0 での値が素数でない組の run は 0 です。

制約

0 ≤ limit ≤ 300

例

例 1
入力:
limit = 3

期待される出力:
expected = [-2, 3, 3]
入力:
long long limit = 3;

期待される出力:
std::vector<long long> expected = {-2, 3, 3};
入力:
long limit = 3;

期待される出力:
long[] expected = new long[] {-2, 3, 3};

解説

a = −2、b = 3 のとき、n = 0, 1, 2, 3 での値は 3, 2, 3, 6 で、素数が3個続きます。これより良い組はなく、より小さい a で同じ個数になる組もないので、答えは [-2, 3, 3] です。

例 2
入力:
limit = 1

期待される出力:
expected = [-1, -1, 0]
入力:
long long limit = 1;

期待される出力:
std::vector<long long> expected = {-1, -1, 0};
入力:
long limit = 1;

期待される出力:
long[] expected = new long[] {-1, -1, 0};

解説

b は −1, 0, 1 のいずれかで、どれも素数ではありません。したがってどの組も run は 0 となり、最小の組が選ばれて [-1, -1, 0] です。

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

n = 0 での値は b なので、素数が1つでも続くには b が素数である必要があります。

ヒント 2

値が素数でなくなるまで n を増やして数えます。負の値や 2 未満の値が出たら、そこで連続は終わりです。

ヒント 3

a と b を小さい順にループし、連続が真に長いときだけ最良の組を更新します。

目安の計算量

時間 O(limit² × run × √V)、追加メモリ O(1)

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

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

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

他の人の解答から学ぶ

コミュニティの解答

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