Superprimzahl-Prüfer

Eine Superprimzahl, auch Superprimzahl oder primindizierte Primzahl genannt, ist eine Primzahl, deren Position in der Folge aller Primzahlen selbst eine Primzahl ist. Die geordneten Primzahlen beginnen mit zwei, drei, fünf, sieben, elf, dreizehn und siebzehn; ihre Indizes (ab eins) laufen von eins bis sieben. Die Indizes zwei, drei, fünf und sieben sind prim, daher sind drei, fünf, elf und siebzehn Superprimzahlen, während zwei (Index eins) und sieben (Index vier) nur gewöhnliche Primzahlen sind. Dieser Prüfer nimmt eine einzelne ganze Zahl n entgegen. Ist n prim, liefert die Antwort den Index von n und ob dieser Index prim ist. Der Algorithmus ist ein deterministisches Sieb ohne Netz, Zufall oder Uhr.

Was eine Superprimzahl ist und wie das Urteil formuliert wird

Eine Superprimzahl ist durch zwei verschachtelte Primzahlbedingungen definiert. Erstens muss n prim sein: Es hat keinen positiven Teiler außer eins und sich selbst. Zweitens muss k ebenfalls prim sein, wenn n die k-te Primzahl in der üblichen steigenden Folge ist — p eins gleich zwei, p zwei gleich drei, p drei gleich fünf, p vier gleich sieben, p fünf gleich elf und so weiter.

Der Index k ist genau der Wert der Primzahlzählfunktion π(n), sobald n prim ist, denn π(n) zählt, wie viele Primzahlen kleiner oder gleich n sind, und n nimmt diesen letzten Platz ein. Die Folge der Superprimzahlen beginnt daher mit drei, fünf, elf, siebzehn, einunddreißig, einundvierzig, neunundfünfzig, siebenundsechzig, dreiundachtzig, einhundertneun: Das sind die Primzahlen an den Primindizes zwei, drei, fünf, sieben, elf, dreizehn, siebzehn, neunzehn, dreiundzwanzig und neunundzwanzig.

Beachten Sie, dass zwei, gleich p eins, entfällt, weil eins kein Primindex ist, und dass sieben, gleich p vier, entfällt, weil vier zusammengesetzt ist.

Eingabevertrag, Grenzen und wie der Index berechnet wird

Nach Annahme der ganzen Zahl prüft die Engine zuerst per Probedivision auf einem Sechserschritt-Rad, ob n prim ist. Scheitert dieser Test, wird die Anfrage mit der Meldung abgewiesen, n sei nicht prim; solche Fehler werden nicht berechnet. Ist n prim, führt die Engine das Sieb des Eratosthenes auf dem Intervall von null bis n aus, zählt, wie viele unmarkierte ganze Zahlen bei oder unter n liegen, und behandelt diese Zählung als den bei eins beginnenden Index k.

Ein zweiter Probetest entscheidet dann, ob k prim ist. Bevorzugen Sie einen eigenen Primzahltest, wenn Sie nur ein Ja oder Nein zu n brauchen, und einen Rechner der n-ten Primzahl, wenn Sie den Index schon kennen und die Primzahl selbst wollen. Diese Seite beantwortet die kombinierte Frage: Ist bei einer gegebenen Primzahl auch ihr Index prim?

Wo ein Superprimzahl-Prüfer seinen Nutzen bringt

Unterricht und Wettbewerbstrainer nutzen einen Superprimzahl-Prüfer, damit Lernende primindizierte Primzahlen einordnen, ohne ein Sieb von Hand zu bauen oder einer undurchsichtigen Onlineliste zu vertrauen. Prüfungsgeneratoren brauchen ein deterministisches Orakel, das Zusammengesetzte als ungültige Eingabe markiert statt still false zurückzugeben, weil ein fehlerhafter Bewerter diese Flagge als erfolgreiche Klassifikation einer Nichtprimzahl lesen könnte. Notizbücher, die eine Spalte von Kandidatenprimzahlen auf Superprimzahlen filtern, können den Vertrag einmal je Zelle aufrufen und den gelieferten Index für eine Prüfspalte behalten.

Koppeln Sie dieses Werkzeug mit einem Primzahltest, wenn Sie Zusammengesetzte klassifizieren statt ablehnen wollen, und mit einem Rechner der n-ten Primzahl, wenn Sie die Folge nach Index durchlaufen wollen statt einen bereits vorliegenden Kandidaten zu prüfen.