Primzahl-Rechner

n ist prim <=> d(n) = 2; previousPrime(97) = 97; nextPrime(97) = 97; nextPrime(1.000.000) = 1.000.003

n

Die ganze Zahl, die geprüft wird — von 2 bis 1.000.000. Die untere Grenze ist bewusst gesetzt und nicht geerbt: Die vorherige Primzahl von 1 existiert nicht, eine Seite, die 1 annähme, hätte also eine Zeile, die sie nicht ehrlich füllen könnte. Ob 1 prim ist, ist eine Definitionsfrage und wird in den Fragen unten beantwortet und nicht vom Rechner

d(n)

Die Anzahl der positiven Teiler, also die erste Zeile des Ergebnisses und der einzige Beleg, auf dem das Urteil ruht. d(n) = 2 heißt, dass genau zwei Zahlen sie teilen, und das ist die Definition von prim. Die Anzahl stammt aus der gemeinsamen Zahlentheorie-Routine, es ist also derselbe Wert, den die Teiler-Seite und die Seite zur Primfaktorzerlegung für dieselbe Eingabe berichten

d(n) = 2

Der Test selbst, als Gleichung hingeschrieben. Er ist eine Äquivalenz und keine Näherung: Eine Zahl ist genau dann prim, wenn sie genau zwei Teiler hat. Für 97 sind die Teiler 1 und 97, die Anzahl ist also 2 und die Einstufung lautet Primzahl. Für 100 sind es 1, 2, 4, 5, 10, 20, 25, 50 und 100, die Anzahl ist also 9 und die Einstufung lautet zusammengesetzte Zahl

previousPrime(n)

Die größte Primzahl, die kleiner oder gleich n ist. Sie ist nach oben einschließlich gemeint, ist n selbst prim, so ist die Antwort n. Für 100 lautet sie 97, für 25 lautet sie 23, für 97 lautet sie 97. Das Intervall ist abgeschlossen, weil die Alternative eine Regel dafür bräuchte, was zu drucken ist, wenn n bereits prim ist, und eine leere Zeile in einer Ergebnisanzeige liest sich als Fehlschlag und nicht als Tatsache

nextPrime(n)

Die kleinste Primzahl, die größer oder gleich n ist, mit derselben einschließenden Regel nach unten. Für 25 ist das 29, für 100 ist das 101 und für 97 ist das 97. Diese Suche kann den Bereich der Eingabe verlassen: nextPrime(1.000.000) ist 1.000.003, eine Primzahl größer als jede Zahl, die die Seite annimmt, und sie wird als Antwort berichtet statt als außerhalb des Bereichs behandelt

1e6 to 1e6 + 100

Die Umgebung der Eingabeobergrenze und der Grund, warum dort oben ein eigener Test nötig ist. Die Primzahlen nahe einer Million sind 999.983 und 1.000.003, die Suche ab 1.000.000 muss also in einer Richtung über eine Million hinausschauen. Die Routine, die Teiler zählt, lehnt Argumente über einer Million ab und würde einen Fehler werfen, deshalb benutzt die Nachbarsuche einen eigenen Test ohne diese Grenze — und beide müssen dort übereinstimmen, wo sie sich überschneiden, und genau das prüfen die Primzahlzeilen in den Beispielen

Einen Modul zu wählen ist der praktischste Grund, eine Primzahl nahe einer selbst gewählten Zahl zu wollen. Die Anzahl der Plätze in einer Hash-Tabelle wird üblicherweise als Primzahl genommen, weil ein Primzahl-Modul Schlüssel, die einen gemeinsamen Faktor teilen, auseinanderzieht, statt sie kollidieren zu lassen; eine Tabelle mit 1.000 Plätzen schickt jedes Vielfache von 25 in dieselben wenigen Plätze, eine mit 997 Plätzen nicht. Dieselbe Überlegung gilt überall dort, wo ein Zähler umläuft: Eine Primzahl als Zykluslänge vermeidet, dass sie mit regelmäßigen Mustern in den Daten in Resonanz gerät. Die Kryptografie ist der andere große Bereich, in dem Schlüssel aus Primzahlen gebaut werden, die sowohl sehr groß als auch weit auseinander liegen, und die Sicherheit ruht darauf, wie schwer es ist, ihr Produkt wieder in die beiden Primzahlen zu zerlegen. Kleinere Anwendungen gibt es überall: eine Teilbarkeitsbehauptung nachprüfen, testen, ob eine Zahl das Produkt zweier Primzahlen ist, und die klassischen Rätsel um Primzahlzwillinge und die Abstände zwischen aufeinanderfolgenden Primzahlen. Geht es dann um die Faktoren selbst, zerlegt die Seite zur Primfaktorzerlegung die Zahl in Primzahlen und ist die natürliche nächste Station; geht es darum, welche Zahlen Ihre Zahl teilen, listet die Teiler-Seite sie alle auf; und ist die geprüfte Zahl nicht prim und Sie wollen wissen, woraus sie besteht, so ist die Teileranzahl auf dieser Seite der erste Hinweis und nicht die vollständige Antwort.

1. Eine Primzahl: 97

   1. Die Teiler von 97 durchprobieren: 2 teilt sie nicht, und 3, 5, 7 und 11 ebenso wenig
   2. An der Wurzel haltmachen: 10 × 10 = 100 liegt schon über 97, es bleibt also nichts mehr zu prüfen
   3. Die einzigen Teiler sind 1 und 97, die Anzahl ist also 2 und die Zahl ist prim
   4. Die vorherige Primzahl ist 97 selbst, weil 97 bereits prim ist und die Suche einschließlich gemeint ist
   5. Die nächste Primzahl ist aus demselben Grund ebenfalls 97

   Die voreingestellte Eingabe und die sauberste Veranschaulichung der einschließenden Regel. Beide Nachbarn kommen als die Zahl selbst zurück, was zunächst so aussieht, als hätten die beiden Zeilen nichts getan. Sie haben: Die größte Primzahl, die nicht größer als 97 ist, ist 97, und die kleinste Primzahl, die nicht kleiner als 97 ist, ist ebenfalls 97. Die Alternative — eine echte Ungleichung — würde diese beiden Zeilen ausgerechnet bei den Eingaben leer lassen, bei denen sich die Seite am sichersten ist, und eine leere Zeile in einer Ergebnisanzeige liest sich als Fehler. Dieser Fall ist außerdem der Punkt, an dem die beiden unabhängigen Tests der Seite zusammentreffen: Die Teileranzahl sagt 2, und die Nachbarsuche stimmt zu, dass 97 prim ist, und beide kommen mit verschiedenem Code dorthin.

2. Eine zusammengesetzte Zahl: 100

   1. 100 ist gerade, also teilt 2 sie; sie endet auf 00, also teilen auch 4, 5, 10, 20, 25 und 50 sie
   2. Die Teiler sind 1, 2, 4, 5, 10, 20, 25, 50 und 100 — neun Stück
   3. Neun ist mehr als zwei, die Einstufung lautet also zusammengesetzte Zahl und nicht Primzahl
   4. Die größte Primzahl bei oder unter 100 ist 97; die kleinste bei oder über 100 ist 101
   5. Beide Nachbarn liegen einen Schritt außerhalb der Zahl, und genau so sieht es aus, wenn eine zusammengesetzte Zahl mitten in einer Lücke liegt

   Der Fall, der zeigt, dass die Nachbarn echte Arbeit leisten. Ist eine Zahl zusammengesetzt, sind die beiden Zeilen die nützliche Ausgabe, weil sie die Frage beantworten, die sich als Nächste stellt: Wenn nicht diese Zahl, welche dann? Siebenundneunzig und einhundertundeins sind die nächstgelegenen Primzahlen, und 100 liegt zwischen ihnen. Auch die Teileranzahl von neun lohnt einen Blick — sie ist ungerade, was genau dann passiert, wenn die Zahl ein Quadrat ist, und 100 ist 10 zum Quadrat. Ein einziger Blick auf die Anzahl verrät also schon etwas über die Gestalt der Zahl, bevor überhaupt faktorisiert wurde.

3. Eine Zahl direkt hinter einer Primzahl: 25

   1. Die Teiler von 25 sind 1, 5 und 25 — drei Stück, weil sich die 5 mit sich selbst paart
   2. Drei ist mehr als zwei, 25 ist also zusammengesetzt
   3. Von 25 abwärts gehen: 24, 23 — 23 ist prim, also ist sie die vorherige Primzahl
   4. Von 25 aufwärts gehen: 26, 27, 28, 29 — 29 ist prim, also ist sie die nächste Primzahl
   5. Der Abstand beträgt hier insgesamt sechs: 23 und 29 liegen um die 25 herum

   Ein Quadrat, weshalb die Teileranzahl ungerade ist, und ein Fall, in dem die beiden Nachbarn sichtbar verschieden weit entfernt liegen — zwei unterhalb und vier oberhalb. Die Anzahl von drei zeigt außerdem, warum zwei die richtige Schwelle ist und nicht etwa die Anzahl der Primfaktoren: 25 hat nur einen einzigen Primfaktor, die 5, ist aber nicht prim, und die Teileranzahl fängt das ab, ohne überhaupt auf die Zerlegung schauen zu müssen.

Die Eingabe muss eine ganze Zahl von 2 bis 1.000.000 sein. Null und eins werden abgelehnt, und die eins aus einem anderen Grund als die null: Bei ihr handelt es sich um eine Definitionsfrage und nicht um eine Zahl außerhalb des Bereichs, und die vorherige Primzahl von 1 existiert nicht. Negative Zahlen werden abgelehnt — die Primzahleigenschaft ist eine Eigenschaft ganzer Zahlen über 1, und auch wenn es in manchen Teilgebieten der Mathematik eine Konvention für negative Primzahlen gibt, übernimmt diese Seite keine. Nachkommastellen werden abgelehnt statt gerundet. Die Obergrenze von einer Million gilt nur für die Eingabe; die beiden Nachbarzeilen dürfen durchaus eine Primzahl außerhalb berichten, und die nächste Primzahl nach einer Million ist 1.000.003, die berichtet und nicht abgelehnt wird. Der Test hinter dem Urteil ist die Probedivision bis zur Wurzel, die bei dieser Größe augenblicklich ist und bei einer Zahl mit zwanzig Stellen hoffnungslos, und diese Grenze ist eine Eigenschaft des Problems und nicht dieser Implementierung. Die Seite berichtet drei Zahlen und eine Einstufung: Sie listet die Teiler nicht selbst auf, zerlegt eine zusammengesetzte Zahl nicht und prüft immer nur eine Zahl statt eines Bereichs. Die Referenztabellen unten sind feste Zeilen und keine Antwort auf Ihre Eingabe. Eine Primzahl wird schließlich als ihre eigene vorherige und nächste Primzahl gemeldet, was eine bewusste Wahl eines abgeschlossenen Intervalls ist und nicht zwei Zeilen, die nichts gefunden haben.

Ist 1 eine Primzahl?

Nein, und sie ist auch keine zusammengesetzte Zahl. Eine Primzahl ist definiert als eine ganze Zahl größer als 1 mit genau zwei positiven Teilern, und 1 hat nur einen einzigen Teiler, sie scheitert also an der Definition in beide Richtungen. Das ist eine bewusst getroffene Entscheidung und kein Versehen: Würde man die 1 als prim zählen, wäre die Aussage, dass jede Zahl genau eine Primfaktorzerlegung hat, nicht mehr wahr, weil man eine Zerlegung beliebig oft mit 1 multiplizieren könnte. Die 1 auszuschließen hält diesen Satz sauber. Weil es eine Frage der Definition und nicht der Rechnung ist, nimmt die Seite die 1 nicht als Eingabe an — die Antwort steht hier.

Warum kommen die vorherige und die nächste Primzahl beide als die Zahl selbst zurück?

Weil beide Suchen einschließlich gemeint sind. Die vorherige Primzahl ist die größte Primzahl, die nicht größer als Ihre Zahl ist, und die nächste Primzahl ist die kleinste, die nicht kleiner als sie ist. Ist die Zahl bereits prim, erfüllt sie beide Beschreibungen, also melden beide Zeilen sie. Die Alternative wäre eine echte Ungleichung, und dann blieben bei einer Primzahleingabe zwei Zeilen ohne Inhalt. Eine leere Zeile in einer Ergebnisanzeige liest sich, als sei etwas schiefgegangen, und die Seite könnte ausgerechnet den Fall nicht beantworten, bei dem sie sich am sichersten ist. Dieselbe Konvention begegnet einem beim Runden, wo eine Zahl, die bereits die Zielgenauigkeit hat, unverändert zurückkommt.

Warum darf die nächste Primzahl größer als eine Million sein, wenn die Eingabe es nicht darf?

Weil die Obergrenze eine Grenze für das ist, was Sie fragen dürfen, und nicht dafür, was die Antwort sein darf. Die nächste Primzahl nach 1.000.000 ist 1.000.003, und sie nicht zu drucken hieße, eine völlig wohldefinierte Frage zu einer Eingabe zu verweigern, die die Seite angenommen hat. Die Nachbarsuche läuft daher mit einem eigenen Test ohne Obergrenze, während die Teileranzahl weiter die gemeinsame Routine benutzt, die nur den Bereich abdeckt. Das bedeutet allerdings, dass zwei Stücke Logik beide entscheiden, ob eine Zahl prim ist — eines mit Grenze, eines ohne —, und sie müssen dort übereinstimmen, wo sie sich überschneiden, was das Beispiel mit der 97 prüft: Die Anzahl sagt 2, und die Nachbarsuche sagt, dass 97 prim ist.

Wofür wird eine Primzahl eigentlich gebraucht?

Vor allem zum Dimensionieren. Hash-Tabellen bekommen üblicherweise eine Primzahl als Anzahl der Plätze, weil ein Primzahl-Modul Schlüssel auseinanderzieht, die einen gemeinsamen Faktor teilen — eine Tabelle mit 1.000 Plätzen schickt jedes Vielfache von 25 in dieselben wenigen Positionen, eine mit 997 Plätzen nicht. Dieselbe Überlegung gilt überall dort, wo ein Zähler umläuft: Eine Primzahl als Zykluslänge vermeidet, dass sie mit regelmäßigen Mustern in den Daten in Resonanz gerät. Die Kryptografie ist der andere große Bereich, in dem Schlüssel aus Primzahlen gebaut werden, die sowohl sehr groß als auch weit auseinander liegen, und die Sicherheit ruht darauf, wie schwer es ist, ihr Produkt wieder in die beiden Primzahlen zu zerlegen. Kleinere Anwendungen gibt es überall: eine Teilbarkeitsbehauptung nachprüfen, testen, ob eine Zahl das Produkt zweier Primzahlen ist, und die klassischen Rätsel um Primzahlzwillinge und die Abstände zwischen aufeinanderfolgenden Primzahlen.

Wie entscheidet die Seite, und wie sicher ist das?

Indem sie Teiler zählt, und das ist exakt und nicht wahrscheinlichkeitsbasiert. Eine Zahl ist genau dann prim, wenn sie genau zwei positive Teiler hat, die Anzahl klärt die Frage also ohne jede Möglichkeit einer falschen Antwort und ohne dass man einem Test vertrauen müsste, der sich täuschen lässt. Gezählt wird durch Probedivision bis zur Wurzel, weshalb eine Million die Obergrenze ist: Darüber wird das Verfahren langsam und nicht unzuverlässig. Für sehr viel größere Zahlen sind die exakten Verfahren tatsächlich undurchführbar und man verwendet wahrscheinlichkeitsbasierte Tests, aber bei dieser Größe gibt es keinen Grund, sich mit weniger als Gewissheit zufriedenzugeben, und die Seite tut das auch nicht.

Warum wird die Teileranzahl gezeigt und nicht nur das Urteil?

Weil die Anzahl der Grund für das Urteil ist, und sie zu zeigen bedeutet, dass die beiden nie uneins werden können — die Einstufung ist keine zweite Rechnung, sondern eine Lesart der Zahl, die daneben gedruckt wird. Sie ist auch für sich nützlich. Eine ungerade Anzahl heißt, dass die Zahl ein Quadrat ist, weil sich die Wurzel dann mit sich selbst paart statt mit einem anderen Teiler. Eine Anzahl von 2 ist die Definition von prim. Eine im Verhältnis zur Größe der Zahl hohe Anzahl sagt, dass sie viele kleine Faktoren hat, also zu der Sorte Zahl gehört, die schnell Teiler sammelt. Und sie verbindet die Seite mit den anderen: Die Seite zur Primfaktorzerlegung berichtet für dieselbe Eingabe dieselbe Teileranzahl, nur aus den Exponenten ausgerechnet, die beiden Seiten prüfen sich also gegenseitig.

• Prime Number — from Wolfram MathWorld (English original; die Definition, der Test über die Teileranzahl und der Grund, aus dem 1 durch ihn ausgeschlossen wird) — Wolfram MathWorld (United States)
• Divisor — from Wolfram MathWorld (English original; was es heißt, dass eine ganze Zahl eine andere ohne Rest teilt, und damit die Größe, auf der das Urteil dieser Seite beruht) — Wolfram MathWorld (United States)
• Perfect Square — from Wolfram MathWorld (English original; die Zahlen, deren Teileranzahl ungerade ist, weil sich die Wurzel mit sich selbst paart statt mit einem anderen Teiler) — Wolfram MathWorld (United States)
• Primzahlen — Mathebibel: die deutschsprachige Einführung in die Primzahlen, ihre Definition, das Sieb des Eratosthenes und die Frage, warum die 1 nicht dazugehört — Mathebibel (Deutschland)