Mittel 0 gelöst 0% Erfolgsquote

Die n-te Primzahl

Gib die n-te Primzahl zurück, wobei 2 die erste ist.

Das lernst du

  • Primzahlen der Reihe nach erzeugen
  • Eine Siebgröße wählen, die für das Ergebnis groß genug ist
  • Probedivision und Sieb miteinander vergleichen

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

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

Die Primzahlen beginnen mit 2, 3, 5, 7, 11, 13, die sechste ist also 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

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.

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.