Problem
Der Reihe nach lauten die Primzahlen 2, 3, 5, 7, 11, 13, … Gesucht ist die Primzahl an der Position n. Für kleine n reicht es, die Zahlen nacheinander zu testen. Bei größeren Eingaben ist ein Sieb über einen ausreichend großen Bereich deutlich schneller.
Implementiere nth_prime(n).
Eingabe
n: Die Position in der Liste der Primzahlen, beginnend bei 1.
Ausgabe
Gib die n-te Primzahl zurück. nth_prime(1) ist 2.
Einschränkungen
1 ≤ n ≤ 100.000
Beispiele
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
Die Primzahlen beginnen mit 2, 3, 5, 7, 11, 13, die sechste ist also 13.
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
Die erste Primzahl ist 2.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Man kann die Primzahlen beim Finden mitzählen, aber jede Zahl per Probedivision zu testen wird bei großem n langsam.
Hinweis 2
Die 100.000. Primzahl liegt unter 1.300.000, ein Sieb dieser Größe reicht also aus.
Hinweis 3
Ist dein Sieb doch zu klein, verdopple seine Größe und versuche es noch einmal.
Erwartete Komplexität
Zeit O(m log log m), zusätzlicher Speicher O(m), wobei m die Siebgröße ist
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.