Primzahl-Rechner

So funktioniert der Primzahl-Rechner

Der Primzahl-Rechner nimmt eine ganze Zahl bis eine Billion und sagt, ob sie eine Primzahl ist. Ist sie keine, zeigt er die Primfaktorzerlegung, die Liste aller Teiler mit ihrer Anzahl und in beiden Fällen die nächste und die vorherige Primzahl. Das deckt die Schulaufgaben "Ist 97 prim?" und "Zerlege 1001 in Primfaktoren" genauso ab wie die Frage, welche Primzahl nach einer Milliarde kommt.

Merksatz: Eine Primzahl hat genau zwei Teiler, 1 und sich selbst, deshalb ist 1 keine Primzahl und 2 die einzige gerade. Die Eselsbrücke für die Prüfung von Hand: Nur bis zur Wurzel testen, denn jeder Teiler über der Wurzel hat einen Partner darunter; für 97 reichen 2, 3, 5 und 7, weil 10 mal 10 schon 100 ist.

Drei Beispiele:

• 97: Primzahl, zwei Teiler, die nächste ist 101, die vorherige 89.
• 1001: keine Primzahl, 7 × 11 × 13, acht Teiler (1, 7, 11, 13, 77, 91, 143, 1001), nächste Primzahl 1009, vorherige 997.
• 2027: Primzahl, nächste 2029, ein Primzahlzwilling, vorherige 2017; auch 1.000.000.007 ist prim, die nächste ist 1.000.000.009.

Formeln: prim, wenn kein Teiler zwischen 2 und √n existiert, Teileranzahl = (e₁ + 1) × (e₂ + 1) × … aus den Exponenten der Primfaktoren, Primzahlzwilling, wenn p und p + 2 beide prim sind. Den größten gemeinsamen Teiler zweier Zahlen aus ihren Primfaktoren rechnet der ggT-kgV-Rechner, Potenzen in der Zerlegung der Potenzrechner.

Wissenswertes zum Thema

Was eine Primzahl ist und warum 1 keine ist

Eine Primzahl ist eine natürliche Zahl größer als 1, die nur durch 1 und sich selbst teilbar ist: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, und es gibt unendlich viele, wie Euklid mit einem Widerspruchsbeweis zeigte, der in drei Zeilen passt. Die 1 ist per Definition ausgeschlossen, weil sonst die Primfaktorzerlegung nicht mehr eindeutig wäre, 6 wäre 2 × 3, aber auch 1 × 2 × 3 und 1 × 1 × 2 × 3; der Fundamentalsatz der Arithmetik sagt, dass jede Zahl über 1 auf genau eine Weise in Primfaktoren zerfällt, und das ist die Grundlage für ggT, kgV, Bruchrechnung und Kryptografie. Die 2 ist die einzige gerade Primzahl, alle anderen sind ungerade, und ab 5 enden sie auf 1, 3, 7 oder 9. Unter 100 gibt es 25 Primzahlen, unter 1.000 sind es 168, unter einer Million 78.498, und der Primzahlsatz sagt, dass der Anteil etwa 1 durch ln(n) ist, bei einer Billion rund jede 28. Zahl. Primzahlzwillinge wie 2027 und 2029 oder 101 und 103 sind Paare mit Abstand 2, und ob es unendlich viele gibt, ist bis heute unbewiesen. Zusammengesetzte Zahlen haben mehr als zwei Teiler, und die Teileranzahl folgt aus den Exponenten der Zerlegung: 1001 = 7¹ × 11¹ × 13¹ hat (1+1)(1+1)(1+1) = 8 Teiler, 360 = 2³ × 3² × 5 hat 4 × 3 × 2 = 24, deshalb war 360 für die Babylonier die praktischste Zahl für den Kreis. Wie sich Teiler zweier Zahlen überschneiden, rechnet der ggT-kgV-Rechner.

Wie der Rechner prüft: Probedivision bis zur Wurzel

Der Rechner nutzt die Probedivision, das älteste und für Zahlen bis eine Billion völlig ausreichende Verfahren: Er testet 2 und 3, danach nur noch Zahlen der Form 6k ± 1, also 5, 7, 11, 13, 17, 19, bis zur Wurzel der eingegebenen Zahl, denn jeder Teiler über der Wurzel hat einen Partner darunter. Für eine Billion ist die Wurzel eine Million, und ein Drittel davon sind Kandidaten, das schafft der Browser in einem Augenblick; deshalb liegt die Grenze bei 10¹², darüber würden die Zahlen in JavaScript ungenau. Die Primfaktorzerlegung läuft gleich: Teilen durch 2, solange es geht, dann durch 3, 5, 7, und was übrig bleibt, ist selbst prim. Die nächste und vorherige Primzahl findet der Rechner, indem er von der Zahl aus hoch- und runterzählt und jede Zahl prüft, bei 1.000.000.007 sind die Nachbarn 1.000.000.009 und 999.999.937, und die Lücken zwischen Primzahlen wachsen im Schnitt mit dem Logarithmus, bei einer Milliarde etwa 21. Für Zahlen mit hunderten Stellen, wie in der Verschlüsselung, taugt die Probedivision nicht, dort arbeiten Miller-Rabin und andere Wahrscheinlichkeitstests, und das Faktorisieren großer Zahlen gilt als praktisch unmöglich, darauf beruht RSA. Der Rechner zeigt die Zerlegung mit Potenzen, 360 = 2³ × 3² × 5, und den Wert einer solchen Potenz rechnet der Potenzrechner.

Primzahlen prüfen von Hand: die Teilbarkeitsregeln

Für Zahlen bis etwa 200 reichen die Teilbarkeitsregeln: Durch 2, wenn die letzte Ziffer gerade ist; durch 3, wenn die Quersumme durch 3 teilbar ist; durch 5 bei Endziffer 0 oder 5; durch 7 mit dem Trick, die letzte Ziffer zu verdoppeln und vom Rest abzuziehen, bei 1001 ist das 100 - 2 = 98 = 14 × 7; durch 11, wenn die alternierende Quersumme durch 11 teilbar ist, bei 1001 ist 1 - 0 + 0 - 1 = 0. Dann bleibt die Wurzelregel: Für 97 bis 9 testen, 2, 3, 5, 7 fallen durch, prim; für 143 bis 11, und 11 × 13 = 143, nicht prim; für 221 bis 14, und 13 × 17 = 221. Die typischen Fallen sind 91 = 7 × 13, 119 = 7 × 17, 133 = 7 × 19 und 221, die alle aussehen wie Primzahlen, und 2 und 3, die so klein sind, dass man sie vergisst. Das Sieb des Eratosthenes liefert alle Primzahlen bis 100 in fünf Minuten: alle Zahlen aufschreiben, Vielfache von 2, 3, 5 und 7 streichen, und was übrig bleibt, ist prim, weil 11 × 11 schon über 100 liegt. Die Primfaktorzerlegung von Hand geht mit dem Baumdiagramm, 1001 in 7 × 143, 143 in 11 × 13, fertig. Für ggT und kgV braucht man die Zerlegung beider Zahlen, und den Rechenweg zeigt der ggT-kgV-Rechner; beim Kürzen von Brüchen hilft sie dem Bruchrechner.

Ein Stück Geschichte: Vom Sieb des Eratosthenes zur Verschlüsselung

Euklid bewies um 300 v. Chr. im neunten Buch der Elemente, dass es unendlich viele Primzahlen gibt, und Eratosthenes von Kyrene, der Bibliothekar von Alexandria, der auch den Erdumfang maß, gab um 240 v. Chr. dem Sieb seinen Namen. Dann ruhte das Thema fast zwei Jahrtausende, bis Pierre de Fermat 1640 seinen kleinen Satz formulierte und Marin Mersenne die Zahlen 2ⁿ - 1 untersuchte, die bis heute die größten bekannten Primzahlen liefern. Euler bewies 1737 mit der Zeta-Funktion erneut die Unendlichkeit, Gauß vermutete mit 15 Jahren den Primzahlsatz, den Hadamard und de la Vallée Poussin 1896 bewiesen, und Riemann stellte 1859 die Hypothese über die Nullstellen der Zeta-Funktion auf, für deren Beweis seit 2000 eine Million Dollar ausgesetzt sind. 1977 bauten Rivest, Shamir und Adleman aus der Schwierigkeit, große Zahlen zu faktorisieren, das RSA-Verfahren, das seitdem Online-Banking und HTTPS schützt: Zwei Primzahlen mit je 300 Stellen zu multiplizieren dauert Mikrosekunden, das Produkt wieder zu zerlegen würde mit heutiger Technik länger dauern als das Universum alt ist. Die größte bekannte Primzahl hat seit Oktober 2024 über 41 Millionen Stellen, 2¹³⁶.²⁷⁹.⁸⁴¹ - 1, gefunden mit Grafikkarten im GIMPS-Projekt. Und 2027, das Jahr nach dem nächsten, ist prim, das letzte Primzahljahr war 2017, das nächste nach 2027 wird 2029 sein.

Praktische Tipps

Testen Sie von Hand nur bis zur Wurzel, das spart die meiste Arbeit. Prüfen Sie zuerst 2, 3 und 5 über die Endziffer und Quersumme. Merken Sie sich die falschen Freunde 91, 119, 133 und 221. Nutzen Sie den Rechner für die Zerlegung, wenn Sie ggT, kgV oder das Kürzen eines Bruchs brauchen. Zählen Sie Teiler über die Exponenten, nicht durch Aufschreiben. Lernen Sie die 25 Primzahlen bis 100 auswendig, sie reichen für fast alle Schulaufgaben. Und geben Sie Zahlen bis eine Billion ohne Punkte ein, 1000000007. Welche Zahl in einer Reihe die Ausnahme ist, lässt sich mit der Zerlegung oft schneller sehen als mit dem Taschenrechner.