問題
素数を小さい順に並べると 2, 3, 5, 7, 11, 13, … となります。位置 n が与えられたとき、その位置にある素数を返してください。n が小さければ1つずつ素数判定しても間に合いますが、大きな入力では、十分な大きさの範囲でエラトステネスの篩を使うほうがはるかに高速です。
nth_prime(n) を実装してください。
入力
n:素数の列における位置(1 から数えます)。
出力
n 番目の素数を返してください。nth_prime(1) は 2 です。
制約
1 ≤ n ≤ 100,000
例
例 1
入力:
n = 6
期待される出力:
expected = 13
入力:
long long n = 6;
期待される出力:
long long expected = 13;
入力:
long n = 6;
期待される出力:
long expected = 13;
解説
素数は 2, 3, 5, 7, 11, 13 と続くので、6番目は 13 です。
例 2
入力:
n = 1
期待される出力:
expected = 2
入力:
long long n = 1;
期待される出力:
long long expected = 2;
入力:
long n = 1;
期待される出力:
long expected = 2;
解説
最初の素数は 2 です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
見つけた素数を数えていく方法でも解けますが、すべての数を試し割りしていると、n が大きいときに遅くなります。
ヒント 2
100,000 番目の素数は 1,300,000 未満なので、その大きさの篩があれば十分です。
ヒント 3
篩が小さすぎたら、サイズを2倍にしてやり直しましょう。
目安の計算量
時間 O(m log log m)、追加メモリ O(m)(m は篩のサイズ)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。