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

Nth Prime

Return the nth prime number, counting 2 as the first.

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

  • Generate primes in order
  • Choose a sieve size large enough for the answer
  • Compare trial division with a sieve

問題

翻訳を表示

The primes in order are 2, 3, 5, 7, 11, 13, … Given a position n, return the prime at that position. Testing numbers one by one works for small n; for the larger inputs a sieve over a range that is big enough is much faster.

Implement nth_prime(n).

Input

n: The position in the list of primes, starting at 1.

Output

Return the nth prime. nth_prime(1) is 2.

制約

1 ≤ n ≤ 100,000

例

例 1
入力:
n = 6

期待される出力:
expected = 13
入力:
long long n = 6;

期待される出力:
long long expected = 13;
入力:
long n = 6;

期待される出力:
long expected = 13;

解説

The primes start 2, 3, 5, 7, 11, 13, so the sixth one is 13.

例 2
入力:
n = 1

期待される出力:
expected = 2
入力:
long long n = 1;

期待される出力:
long long expected = 2;
入力:
long n = 1;

期待される出力:
long expected = 2;

解説

The first prime is 2.

解き方のヒント

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

ヒント 1

Counting primes as you find them works, but testing every number by trial division gets slow for large n.

ヒント 2

The 100,000th prime is below 1,300,000, so a sieve of that size is enough.

ヒント 3

If your sieve turns out too small, double it and try again.

目安の計算量

O(m log log m) time, O(m) extra space, where m is the sieve size

参考資料

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

ランキング

全体ランキング

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

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

他の人の解答から学ぶ

コミュニティの解答

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