Primzahlprüfer
Prüfen Sie, ob eine Zahl eine Primzahl ist, sehen Sie ihre vollständige Primfaktorzerlegung und die benachbarten Primzahlen, sieben Sie alle Primzahlen in einem Bereich oder testen Sie eine Mersenne-Zahl 2ᵖ − 1 mit dem Lucas-Lehmer-Test auf Primalität.
Verfasst von Suhaib Hassan. Jeder Algorithmus ist Standard und wurde unabhängig nachgeprüft. Unsere Methodik.
Der Primzahltest verwendet einen deterministischen Miller–Rabin-Test (exakt, nicht probabilistisch, für jede ganze Zahl unter 2⁶⁴); die Faktorisierung nutzt Probedivision; Mersenne-Zahlen werden mit dem Lucas-Lehmer-Test geprüft.
Er zeigt die tatsächlichen Teilbarkeitsprüfungen und die Lucas-Lehmer-Iterationen – nicht nur ein Ja oder Nein.
—
Primzahlen in der Nähe von n
Primzahllücken rund um die geprüfte Zahl.
Rechenweg Schritt für Schritt
—
Rechenbeispiele
Eine bekannte Primzahl
Ist 104.729 eine Primzahl?
Ja – es ist die 10.000. Primzahl
Eine Carmichael-Zahl
Ist 561 eine Primzahl?
Nein – zusammengesetzt, auch wenn sie bekanntermaßen den einfacheren Fermat-Test für jede Basis besteht
Eine Mersenne-Primzahl
Ist 2¹³ − 1 = 8191 eine Primzahl?
Ja – 8191 ist eine Primzahl
Was ist eine Primzahl?
Eine Primzahl ist eine ganze Zahl größer als 1 mit genau zwei positiven Teilern: 1 und sich selbst. Jede andere ganze Zahl größer als 1 ist zusammengesetzt, und nach dem Fundamentalsatz der Arithmetik lässt sich jede zusammengesetzte Zahl eindeutig in Primzahlen zerlegen.
So funktionieren die Tests
- Probedivision: Prüfen Sie die Teilbarkeit durch jede ganze Zahl bis √n; teilt keine ohne Rest, ist n eine Primzahl.
- Miller–Rabin (hier deterministisch): ein schneller Primzahltest, der mit einer festen, bewiesenen Menge von Zeugenbasen für jedes n unter 2⁶⁴ ein exaktes Ja oder Nein liefert – ganz ohne Zufall oder Unsicherheit.
- Lucas–Lehmer: Für Mersenne-Zahlen Mₚ = 2ᵖ − 1 mit primem p iteriert man s ← s² − 2 (mod Mₚ) ab s = 4; Mₚ ist genau dann prim, wenn das Ergebnis nach p − 2 Schritten 0 ist.
Von Suhaib Hassan · Geprüft am 29. September 2026 · So prüft CalculatePilot Formeln →
Quellen
- Pomerance, C., Selfridge, J. L., & Wagstaff, S. S. (1980). The pseudoprimes to 25·10⁹. Mathematics of Computation 35(151), 1003–1026.
- Crandall, R., & Pomerance, C. (2005). Prime Numbers: A Computational Perspective (2nd ed.). Springer, Kapitel 3–4 (Miller–Rabin, Lucas–Lehmer).
- ISO 80000-2:2019, Abschnitt 6 (Notation der Zahlentheorie).
Häufig gestellte Fragen
Ist 1 eine Primzahl?
Nein. Per Definition hat eine Primzahl genau zwei verschiedene positive Teiler; 1 hat nur einen (sich selbst) und gilt daher weder als Primzahl noch als zusammengesetzte Zahl.
Warum muss die Probedivision nur bis √n prüfen?
Wenn n = a × b mit a ≤ b gilt, dann ist a ≤ √n. Wird also bis √n kein Teiler gefunden, kann es auch jenseits von √n keinen geben – jede zusammengesetzte Zahl hat mindestens einen Faktor, der höchstens so groß ist wie ihre Quadratwurzel.
Was macht Carmichael-Zahlen so tückisch?
Eine Carmichael-Zahl ist zusammengesetzt, erfüllt aber den kleinen Fermatschen Satz für jede zu ihr teilerfremde Basis, sodass der einfache Fermat-Test sie fälschlich als Primzahl einstuft. Miller–Rabin mit geeigneten Zeugen erkennt sie korrekt als zusammengesetzt.
Was ist eine Mersenne-Primzahl?
Eine Primzahl der Form 2ᵖ − 1. Dabei muss p selbst eine Primzahl sein (eine notwendige, aber nicht hinreichende Bedingung) – zum Beispiel ist 2¹¹ − 1 = 2047 = 23 × 89 zusammengesetzt, obwohl 11 eine Primzahl ist. Die größten heute bekannten Primzahlen sind fast alle Mersenne-Primzahlen, gefunden mit dem Lucas-Lehmer-Test.
Wie viele Primzahlen gibt es?
Unendlich viele – bewiesen von Euklid um 300 v. Chr.: Nimmt man eine endliche Liste von Primzahlen an und multipliziert sie miteinander plus 1, entsteht stets eine Zahl mit einem Primfaktor, der nicht in der Liste steht – ein Widerspruch.
Warum sind Primzahlen in der Kryptografie wichtig?
Die RSA-Verschlüsselung beruht darauf, dass die Multiplikation zweier großer Primzahlen schnell geht, die Zerlegung ihres Produkts in diese Primzahlen aber rechnerisch sehr aufwendig ist – diese Asymmetrie sorgt für die Sicherheit der Verschlüsselung.
Verwandte Rechner
Weiter mit Zahlentheorie.