Primzahl-Prüfer
Gib eine beliebige ganze Zahl ein, sogar eine mit 60 Stellen, um herauszufinden, ob sie eine Primzahl ist, und sieh ihre Primfaktorzerlegung, ihren Faktorbaum und ihre Teiler, oder liste alle Primzahlen in einem Bereich auf.
Zuletzt aktualisiert:
Alle Teiler
Faktorbaum
Bereichsgröße bis 10,000,000 Zahlen, Ende bis 10¹⁴. Verwendet ein segmentiertes Sieb des Eratosthenes.
Anleitung: Primzahl-Prüfer
- Gib eine Zahl oder einen Ausdruck wie 2^31-1 ein oder tippe auf eines der Beispiele.
- Drücke auf Primzahl prüfen, um zu sehen, ob sie eine Primzahl ist und warum, mit Rechenweg.
- Lies die Zerlegung, die Teiler und den Faktorbaum bei zusammengesetzten Zahlen und lade den Baum als SVG herunter.
- Wechsle zu Primzahlen im Bereich, gib Anfang und Ende ein und drücke auf Primzahlen finden.
- Kopiere oder lade die vollständige Liste der Primzahlen herunter.
So funktioniert der Primzahltest
Eine Primzahl ist eine ganze Zahl größer als 1, deren einzige Teiler 1 und sie selbst sind. Für kleine Zahlen nutzt der Prüfer die Probedivision: Wenn keine Primzahl bis √n die Zahl n teilt, ist n eine Primzahl. Zum Beispiel ist √97 ≈ 9.8, und weder 2, 3, 5 noch 7 teilt 97, also ist 97 eine Primzahl.
Für große Zahlen nutzt er den Miller–Rabin-Test mit exakter Ganzzahlarithmetik. Schreibe n − 1 = 2ˢ × d mit ungeradem d; für jede Basis a besteht n, wenn ad ≡ 1 (mod n) oder a2ʳd ≡ −1 (mod n) für ein r < s gilt. Der Test mit den 13 Primbasen 2 bis 41 ist nachweislich deterministisch für jedes n unter 3.3 × 10²⁴. Darüber werden 25 Basen verwendet und das Ergebnis wird als starke wahrscheinliche Primzahl ausgewiesen (die Fehlerwahrscheinlichkeit ist astronomisch klein).
Primfaktorzerlegung und Faktorbäume
Jede ganze Zahl größer als 1 lässt sich auf genau eine Weise als Produkt von Primzahlen schreiben (der Fundamentalsatz der Arithmetik). Das Tool teilt zuerst kleine Primzahlen ab und zerlegt große zusammengesetzte Teile dann mit Pollards Rho (Brents Variante), das Faktoren 20-stelliger Zahlen in Millisekunden findet. Beispiel: 360 = 2 × 180 = 2 × 2 × 90 = … = 2³ × 3² × 5.
Aus der Zerlegung n = p₁a × p₂b × … ergibt sich die Anzahl der Teiler als (a + 1)(b + 1)…, also hat 360 genau 4 × 3 × 2 = 24 Teiler. Die eulersche Phi-Funktion φ(n) zählt die Zahlen bis n, die keinen gemeinsamen Faktor mit n haben.
Wie viele Primzahlen gibt es?
| Bis | Anzahl der Primzahlen π(n) | Größte Primzahl unter |
|---|---|---|
| 10 | 4 | 7 |
| 100 | 25 | 97 |
| 1,000 | 168 | 997 |
| 10,000 | 1,229 | 9,973 |
| 100,000 | 9,592 | 99,991 |
| 1,000,000 | 78,498 | 999,983 |
| 10,000,000 | 664,579 | 9,999,991 |
Der Primzahlsatz besagt, dass π(n) ungefähr n ÷ ln(n) beträgt. Primzahlen werden also langsam seltener, hören aber nie auf: Euklid bewies, dass es unendlich viele gibt. Die Bereichssuche nutzt ein segmentiertes Sieb des Eratosthenes und streicht die Vielfachen jeder Primzahl bis √(Ende).
Besondere Zahlenarten
- Primzahlzwillinge unterscheiden sich um 2, wie 11 und 13 oder 101 und 103.
- Mersenne-Primzahlen haben die Form 2ᵖ − 1, etwa 2⁶¹ − 1 = 2,305,843,009,213,693,951.
- Carmichael-Zahlen wie 561 = 3 × 11 × 17 bestehen den einfachen Fermat-Test für jede zu ihnen teilerfremde Basis, weshalb stattdessen Miller–Rabin verwendet wird.
- Halbprimzahlen sind Produkte zweier Primzahlen – die Grundlage der RSA-Verschlüsselung.
Häufige Fragen
Woran erkenne ich, ob eine Zahl eine Primzahl ist?
Prüfe, ob eine Primzahl bis zu ihrer Quadratwurzel sie ohne Rest teilt. Wenn keine es tut, ist sie eine Primzahl. Zum Beispiel ist 91 keine Primzahl, weil 7 × 13 = 91, aber 89 ist eine Primzahl, weil weder 2, 3, 5 noch 7 sie teilt.
Ist 1 eine Primzahl?
Nein. Eine Primzahl muss genau zwei verschiedene Teiler haben: 1 und sich selbst. Die Zahl 1 hat nur einen Teiler, ist also weder Primzahl noch zusammengesetzt. Die kleinste Primzahl ist 2, die einzige gerade Primzahl.
Wie große Zahlen kann ich prüfen?
Bis zu 60 Stellen. Zahlen unter 3.3 × 10²⁴ werden exakt als Primzahl oder zusammengesetzt nachgewiesen; größere nutzen zusätzliche Miller–Rabin-Runden und werden als starke wahrscheinliche Primzahlen ausgewiesen. Das Zerlegen sehr großer Zahlen mit zwei großen Primfaktoren kann länger dauern, als der Browser erlaubt.
Was ist ein Faktorbaum?
Ein Diagramm, das eine Zahl in zwei Faktoren aufteilt und dann jeden zusammengesetzten Faktor erneut aufteilt, bis an den Blättern nur noch Primzahlen stehen. Multipliziert man die grünen Primzahlblätter, erhält man wieder die ursprüngliche Zahl.
Was ist der Miller–Rabin-Test?
Ein schneller Primzahltest auf Basis modularer Exponentiation. Jede Basis beweist entweder, dass eine Zahl zusammengesetzt ist, oder lässt sie bestehen. Mit der richtigen Auswahl an Basen ist er für alle Zahlen unter einer bekannten Schranke deterministisch.
Wird meine Zahl irgendwohin gesendet?
Nein. Alle Berechnungen laufen in deinem Browser mit JavaScript BigInt; nichts wird hochgeladen.
Werden alle Tools auf FreeToolCabin auf Qualität und Genauigkeit getestet?
Ja. Jedes Tool auf der Website durchläuft automatische Tests in echten Browsern, die prüfen, ob das Ergebnis stimmt und keine Fehler auftreten. Wenn du einen Fehler findest oder einen Vorschlag hast, schreib uns an [email protected] – wir sehen es uns an.