So verwenden Sie es
- Tragen Sie eine ganze Zahl von 1 bis 10¹⁵ in Ganze Zahl ein. Leerzeichen innerhalb der Zahl sind erlaubt.
- Lesen Sie Primfaktorzerlegung und die Tabelle der Primfaktoren mit ihren Exponenten ab.
- Prüfen Sie Anzahl der Teiler, Summe der Teiler und Ist sie eine Primzahl?.
- Gehen Sie den Rechenweg durch, um den Faktorbaum Schritt für Schritt zu sehen.
So werden die Primfaktoren gefunden
Die Probedivision teilt die Zahl durch 2, 3 und 5 und danach durch die Zahlen, die zu 30 teilerfremd sind (7, 11, 13, 17, 19, 23, 29 und so weiter). Jeder Teiler wird so lange abgespalten, wie die Division aufgeht. Die Suche endet bei 10.000 oder wenn das Quadrat des nächsten Kandidaten größer ist als der Rest.
Der Rest ist entweder 1, eine Primzahl oder eine zusammengesetzte Zahl mit zwei Primfaktoren über 10.000. Primzahlen erkennt der Miller-Rabin-Test. Eine zusammengesetzte Zahl wird mit dem Pollard-Rho-Verfahren zerlegt, das einen Teiler durch eine Suche in Zyklen findet.
Teiler und ihre Summe
Ist n = p₁^e₁ × p₂^e₂ × …, dann hat n (e₁ + 1) × (e₂ + 1) × … Teiler. Die Summe der Teiler ist das Produkt der Summen 1 + p + … + p^e für jede Primzahlpotenz.
Eine Primzahl hat zwei Teiler, 1 und sich selbst. Ihre Teilersumme ist deshalb um eins größer als die Primzahl selbst. Die Zahl 1 hat nur einen Teiler und ist keine Primzahl.
n = p₁^e₁ × … × p_k^e_k
Anzahl der Teiler = (e₁ + 1) × … × (e_k + 1)
Summe der Teiler = (1 + p₁ + … + p₁^e₁) × … × (1 + p_k + … + p_k^e_k)Was der Rechner nicht abdeckt
- Zahlen über 10¹⁵ sowie negative Zahlen, Dezimalzahlen und Brüche.
- Die Zerlegung vieler Zahlen auf einmal. Für eine Liste von Zahlen eignet sich ggT und kgV berechnen, das die Primfaktoren jeder Zahl zeigt.
- Ein Beweis der Primzahleigenschaft für Zahlen über 3,3 × 10²⁴. Der Test hier ist nur unterhalb dieser Grenze exakt.
Rechenbeispiel: 600851475143
Die Probedivision entfernt 71, 839, 1471 und 6857, jeweils einmal. Also ist 600851475143 = 71 × 839 × 1471 × 6857. Alle Exponenten sind 1, daher gibt es 2 × 2 × 2 × 2 = 16 Teiler.
Die Summe der Teiler ist (1 + 71) × (1 + 839) × (1 + 1471) × (1 + 6857) = 72 × 840 × 1472 × 6858 = 610.544.148.480. Die Zahl ist zusammengesetzt, also keine Primzahl.
| Ergebnis | |
|---|---|
| Primfaktorzerlegung | 71 × 839 × 1471 × 6857 |
| Anzahl der Teiler | 16 |
| Summe der Teiler | 610.544.148.480 |
| Ist sie eine Primzahl? | Nein |
Häufig gestellte Fragen
Was ist eine Primfaktorzerlegung?
Sie schreibt eine ganze Zahl als Produkt von Primzahlen. Zum Beispiel ist 84 = 2 × 2 × 3 × 7, geschrieben als 2² × 3 × 7, wobei die 2 den Exponenten 2 hat.
Warum bricht der Rechner die Probedivision bei 10.000 ab?
Probedivision ist bei großen Primzahlen langsam. Nach den Divisionen bis 10.000 wird der Rest mit dem Miller-Rabin-Test geprüft und mit dem Pollard-Rho-Verfahren zerlegt. Unterhalb von 10¹⁵ hat der Rest höchstens drei Primfaktoren, und beide Verfahren finden sie schnell.
Ist 1 eine Primzahl?
Nein. Eine Primzahl hat genau zwei Teiler, die 1 hat nur einen. Die Zahl 1 ist daher weder prim noch zusammengesetzt und hat keine Primfaktoren.
Wie genau ist der Primzahltest?
Für alle Zahlen unter 3,3 × 10²⁴ ist der Test exakt, weil die Basen 2 bis 41 in diesem Bereich die Primzahleigenschaft sicher entscheiden. Der Rechner nimmt allerdings nur Zahlen bis 10¹⁵ an.
Was sagt mir die Anzahl der Teiler?
Sie zählt alle ganzen Zahlen, die die Zahl genau teilen, einschließlich 1 und der Zahl selbst. Sie ergibt sich aus den Exponenten: Man addiert zu jedem Exponenten 1 und multipliziert die Ergebnisse.
Werden die eingegebenen Zahlen an einen Server geschickt?
Nein. Die Zerlegung läuft in Ihrem Browser, und nichts, was Sie eingeben, wird an uns übermittelt.
Quellen
- Wikipedia (englisch): Integer factorization, mit Probedivision und Pollard-Rho-Verfahren
- Wikipedia (englisch): Pollard's rho algorithm
- Wikipedia (englisch): Miller-Rabin primality test
- Wikipedia (englisch): Divisor function, Anzahl und Summe der Teiler
Zahlen und Text zuletzt geprüft: Dienstag, 10. November 2026.