Mittel 0 gelöst 0% Erfolgsquote

Nth Prime

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

Das lernst du

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

Problem

Übersetzung anzeigen

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.

Einschränkungen

1 ≤ n ≤ 100,000

Beispiele

Beispiel 1
Eingabe:
n = 6

Erwartete Ausgabe:
expected = 13
Eingabe:
long long n = 6;

Erwartete Ausgabe:
long long expected = 13;
Eingabe:
long n = 6;

Erwartete Ausgabe:
long expected = 13;

Erläuterung

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

Beispiel 2
Eingabe:
n = 1

Erwartete Ausgabe:
expected = 2
Eingabe:
long long n = 1;

Erwartete Ausgabe:
long long expected = 2;
Eingabe:
long n = 1;

Erwartete Ausgabe:
long expected = 2;

Erläuterung

The first prime is 2.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

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

Hinweis 2

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

Hinweis 3

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

Erwartete Komplexität

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

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.