Primzahl-Rechner
Prüfen Sie, ob eine Zahl mit bis zu 40 Stellen eine Primzahl ist. Mit Primfaktorzerlegung, Teilern, nächster und vorheriger Primzahl und allen Primzahlen in einem Bereich.
So funktioniert die Primzahlprüfung
Eine Primzahl ist eine ganze Zahl größer als 1 mit genau zwei Teilern: 1 und sich selbst. 2, 3, 5, 7 und 11 sind Primzahlen. Eine Zahl mit mehr Teilern, wie 12 (1, 2, 3, 4, 6, 12), ist zusammengesetzt. 0 und 1 sind weder prim noch zusammengesetzt. Jede ganze Zahl über 1 lässt sich auf genau eine Weise als Produkt von Primzahlen schreiben, zum Beispiel 360 = 2³ × 3² × 5.
Um n zu prüfen, teilt man es durch jede Primzahl bis √n. Wenn n = a × b, muss a oder b höchstens √n sein. Teilt keine Primzahl bis √n die Zahl n, ist n prim. Für 221 gilt √221 ≈ 14,9, und 221 ÷ 13 = 17, also ist 221 keine Primzahl. Dieser Rechner nutzt die Probedivision für Zahlen bis eine Billion.
Für größere Zahlen ist die Probedivision zu langsam, daher nutzt der Rechner den Miller-Rabin-Test. Er prüft eine Eigenschaft, die jede Primzahl hat, mit mehreren Testwerten, den Basen. Mit den ersten 13 Primzahlen als Basen ist der Test für alle Zahlen unter etwa 3,3 × 10²⁴ nachweislich korrekt. Darüber werden 20 Basen genutzt, und das Ergebnis heißt wahrscheinliche Primzahl. Zusammengesetzte Zahlen werden mit Pollards Rho-Methode in Faktoren zerlegt.
Haftungsausschluss: Dieser Rechner führt Standard-Rechenoperationen ausschließlich für allgemeine und schulische Zwecke aus. Wir ersetzen keine fachliche Prüfung — bei Berechnungen, bei denen Genauigkeit entscheidend ist, etwa bei Steuererklärungen, technischen Arbeiten oder wissenschaftlichen Abgaben, überprüfen Sie das Ergebnis bitte unabhängig.
Häufig gestellte Fragen
Über diesen Rechner
Dieser Primzahl-Rechner zeigt sofort, ob eine ganze Zahl eine Primzahl ist. Wenn nicht, sehen Sie ihre Primfaktorzerlegung und ihre Teiler. Er zeigt außerdem die vorherige und die nächste Primzahl, erkennt Primzahlzwillinge und Mersenne-Primzahlen und erklärt jeden Schritt für Zahlen bis eine Billion. Im Tab Primzahlen im Bereich listen Sie alle Primzahlen zwischen zwei Zahlen auf.
Was eine Zahl zur Primzahl macht
Eine Primzahl ist eine ganze Zahl größer als 1 mit genau zwei Teilern: 1 und sich selbst. 2, 3, 5, 7, 11 und 13 sind die ersten Primzahlen. 2 ist die einzige gerade Primzahl, denn jede andere gerade Zahl ist durch 2 teilbar. Eine ganze Zahl über 1, die keine Primzahl ist, heißt zusammengesetzt. 0 und 1 sind weder prim noch zusammengesetzt.
Primzahlen sind die Bausteine aller ganzen Zahlen. Der Fundamentalsatz der Arithmetik besagt, dass sich jede ganze Zahl über 1 auf genau eine Weise als Produkt von Primzahlen schreiben lässt, wenn man die Reihenfolge nicht beachtet. Zum Beispiel ist 360 = 2³ × 3² × 5. Diese Primfaktorzerlegung zeigt der Rechner für zusammengesetzte Zahlen an.
So arbeitet der Rechner
Kleine und mittlere Zahlen (bis eine Billion): Probedivision. Um n zu prüfen, teilt der Rechner n durch jede Primzahl bis √n. Das genügt, denn wenn n = a × b, muss a oder b höchstens √n sein. Teilt keine dieser Primzahlen n ohne Rest, ist n prim. Für 1.000.000.007 gilt √n ≈ 31.623. Der Rechner testet also die 3.401 Primzahlen bis 31.622 und stellt fest, dass keine davon teilt.
Große Zahlen: der Miller-Rabin-Test. Über einer Billion nutzt der Rechner den Miller-Rabin-Test. Jede ungerade Primzahl p besteht eine Prüfung, bei der man p − 1 = 2ˢ × d schreibt und einen Testwert (eine Basis) modulo p hoch d nimmt. Eine zusammengesetzte Zahl fällt bei den meisten Basen durch. Mit den ersten 13 Primzahlen (2 bis 41) als Basen ist der Test für jede Zahl unter etwa 3,3 × 10²⁴ nachweislich korrekt. Für größere Zahlen nutzt der Rechner 20 Basen und kennzeichnet das Ergebnis als wahrscheinliche Primzahl.
Zerlegung: Pollards Rho-Methode. Um eine große zusammengesetzte Zahl zu zerlegen, entfernt der Rechner zuerst kleine Primfaktoren und nutzt dann Pollards Rho-Methode, die einen Faktor viel schneller findet als die Probedivision. Zahlen, deren Primfaktoren alle sehr groß sind, können auf jedem Computer Jahre zur Zerlegung brauchen. Dann zeigt der Rechner den Teil, den er nicht zerlegen konnte.
Primzahlen im Bereich: das Sieb. Der Bereichs-Tab nutzt ein segmentiertes Sieb des Eratosthenes. Es streicht die Vielfachen jeder Primzahl bis √(Bis), und jede übrige Zahl ist prim. So lassen sich bis zu einer Million Zahlen auf einmal prüfen, überall bis eine Billion.
Beispiele
- 221: √221 ≈ 14,9, also testet der Rechner 2, 3, 5, 7, 11 und 13. 221 ÷ 13 = 17, also ist 221 = 13 × 17 zusammengesetzt. Viele halten 221 für prim, weil sie ungerade ist und nicht auf 5 endet.
- 561: 561 = 3 × 11 × 17. Sie ist die kleinste Carmichael-Zahl, eine zusammengesetzte Zahl, die den einfachen Fermat-Test für jede teilerfremde Basis besteht. Der Miller-Rabin-Test hat diese Schwäche nicht.
- 2.147.483.647: das ist 2³¹ − 1, eine Mersenne-Primzahl und der größte Wert einer vorzeichenbehafteten 32-Bit-Ganzzahl in der Programmierung. Der Rechner bestätigt, dass sie prim ist, und kennzeichnet sie als Mersenne-Primzahl.
- 600.851.475.143: = 71 × 839 × 1.471 × 6.857. Ihr größter Primfaktor, 6.857, ist die Lösung eines bekannten Programmierrätsels (Project Euler, Aufgabe 3).
Primzahlen werden mit wachsender Größe seltener, gehen aber nie aus. Der Primzahlsatz besagt, dass in der Nähe einer Zahl n etwa jede ln(n)-te Zahl prim ist. Bei einer Billion ist ln(10¹²) ≈ 27,6, also sollte ein Block von 200.000 Zahlen etwa 7.238 Primzahlen enthalten. Zwischen 999.999.800.000 und 1.000.000.000.000 sind es 7.213, was Sie mit dem Bereichs-Tab prüfen können.
Wo Primzahlen genutzt werden
- Internetsicherheit: Die RSA-Verschlüsselung multipliziert zwei geheime Primzahlen mit je Hunderten von Stellen. Das Produkt ist öffentlich, aber keine bekannte Methode kann es in vertretbarer Zeit zerlegen, und das schützt den Schlüssel.
- Programmierung: Hashtabellen nutzen oft eine Primzahl als Anzahl der Plätze, um Daten gleichmäßig zu verteilen, und Wettbewerbsaufgaben verlangen Ergebnisse oft modulo der Primzahl 1.000.000.007.
- Mathematische Rekorde: Das Projekt GIMPS sucht nach sehr großen Mersenne-Primzahlen. Im Oktober 2024 fand es 2^136.279.841 − 1, eine Primzahl mit mehr als 41 Millionen Stellen.
- Unterricht: Primzahlen finden, Faktorbäume und Teileranzahlen sind Grundthemen in der Schule, und die Schritt-für-Schritt-Erklärung zeigt jede Division.
- Sofortige Primzahlprüfung — Prüft jede ganze Zahl mit bis zu 40 Stellen und zeigt, ob sie prim, zusammengesetzt oder keins von beiden (0 und 1) ist.
- Primfaktorzerlegung und Teiler — Zerlegt zusammengesetzte Zahlen in Primfaktoren mit Exponenten und zeigt die Anzahl der Teiler und die Teiler selbst.
- Schritt für Schritt — Zeigt für Zahlen bis eine Billion √n, die getesteten Primzahlen und die Division, die das Ergebnis beweist.
- Primzahlen im Bereich — Listet alle Primzahlen zwischen zwei Zahlen auf, bis eine Billion und bis zu einer Million Zahlen auf einmal, mit der Anzahl der Primzahlzwillinge.
- Benachbarte und besondere Primzahlen — Zeigt die vorherige und die nächste Primzahl und erkennt Primzahlzwillinge und Mersenne-Primzahlen.