問題
素数をうまく生み出す二次式があります。たとえば 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
例
入力:
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] です。
入力:
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用に調整されています。上記の説明と制約に従ってください。