So funktioniert der Primfaktorzerlegung-Rechner
Du gibst eine ganze Zahl ein und bekommst zwei Antworten auf einmal: ob sie eine Primzahl ist, und falls nicht, wie sie sich vollständig in Primfaktoren zerlegen lässt. Dazu kommt der komplette Rechenweg – erst die Überlegung, wie weit man überhaupt suchen muss, dann die fortgesetzte Division Zeile für Zeile und zum Schluss die Teileranzahl aus den Exponenten. Genau die Schritte, die in der Schule verlangt werden.
Drei Dinge kann dieser Rechner, die reine Zerlegungs-Rechner nicht bieten. Er listet alle Teiler auf und erklärt über die Formel τ = (e₁+1) · (e₂+1) · …, warum es genau so viele sind. Er bildet die Teilersumme und ordnet die Zahl damit als defizient, vollkommen oder abundant ein – die Klassifikation, an der sich die Zahlentheorie seit der Antike abarbeitet. Und er zeigt zu jeder Zahl die benachbarten Primzahlen, die greifenden Teilbarkeitsregeln, die Eulersche Phi-Funktion und den Test auf Quadrat- und Kubikzahl. Gerechnet wird exakt bis eine Billion.
Die Formeln
Anzahl Teiler: τ(n) = (e₁+1) · (e₂+1) · … · (ek+1)
Teilersumme: σ(n) = Π (piei+1 − 1) ÷ (pi − 1)
Eulersche Phi-Funktion: φ(n) = n · Π (1 − 1/pi)
Der Fundamentalsatz der Arithmetik sagt: Jede ganze Zahl größer als 1 lässt sich als Produkt von Primzahlen schreiben, und zwar auf genau eine Art – von der Reihenfolge abgesehen. Deshalb spricht man von der Primfaktorzerlegung und nicht von einer. Genau dieser Eindeutigkeit wegen zählt die 1 nicht zu den Primzahlen: Wäre sie prim, könnte man beliebig viele Einsen anhängen und die Zerlegung wäre nicht mehr eindeutig.
Beispiele aus dem Rechner
| Zahl | Primfaktoren | Teiler | Teilersumme σ | Einordnung |
|---|---|---|---|---|
| 6 | 2 · 3 | 4 | 12 | vollkommen |
| 28 | 2² · 7 | 6 | 56 | vollkommen |
| 60 | 2² · 3 · 5 | 12 | 168 | abundant |
| 97 | Primzahl | 2 | 98 | defizient |
| 100 | 2² · 5² | 9 | 217 | abundant |
| 360 | 2³ · 3² · 5 | 24 | 1.170 | abundant |
| 1.024 | 2¹⁰ | 11 | 2.047 | defizient |
| 9.973 | Primzahl | 2 | 9.974 | defizient |
| 1.000.003 | Primzahl | 2 | 1.000.004 | defizient |
| Alle Werte aus Durchläufen des Rechners auf dieser Seite. | ||||
Warum die Suche an der Wurzel endet
Um zu prüfen, ob 9.973 eine Primzahl ist, muss man nicht 9.971 Divisionen durchführen, sondern nur rund 25. Der Grund ist einfach: Teiler treten immer paarweise auf. Ist a ein Teiler von n, dann ist auch n ÷ a einer – und von diesen beiden ist mindestens einer höchstens so groß wie die Wurzel aus n. Findet sich bis zur Wurzel kein Teiler, kann es darüber auch keinen mehr geben, weil jeder große Teiler einen kleinen Partner bräuchte.
Der Rechner geht noch einen Schritt weiter und testet nach 2 und 3 nur noch Kandidaten der Form 6k−1 und 6k+1, also 5, 7, 11, 13, 17, 19 und so weiter. Alle übrigen Zahlen sind selbst durch 2 oder 3 teilbar und können deshalb keinen neuen Primteiler beisteuern. Das spart zwei Drittel aller Versuche – aus einer Million Kandidaten werden rund 333.000.
Teilbarkeitsregeln zum Kopfrechnen
| Teiler | Regel | Beispiel 3.960 |
|---|---|---|
| 2 | Endziffer ist gerade | 0 – geht auf |
| 3 | Quersumme durch 3 teilbar | 3+9+6+0 = 18 – geht auf |
| 4 | letzte zwei Ziffern durch 4 teilbar | 60 – geht auf |
| 5 | Endziffer 0 oder 5 | 0 – geht auf |
| 6 | durch 2 und durch 3 | beides – geht auf |
| 8 | letzte drei Ziffern durch 8 teilbar | 960 – geht auf |
| 9 | Quersumme durch 9 teilbar | 18 – geht auf |
| 11 | alternierende Quersumme durch 11 teilbar | 0−6+9−3 = 0 – geht auf |
Diese Regeln ersetzen keine Zerlegung, aber sie beschleunigen sie enorm. Wer 3.960 zerlegen soll, sieht mit einem Blick, dass 8, 9 und 5 hineinpassen, und ist nach drei Divisionen fertig. Der Rechner zeigt dir für jede Eingabe an, welche Regeln greifen.
Vollkommen, defizient, abundant
Addiert man alle echten Teiler einer Zahl, also alle außer der Zahl selbst, ergibt sich eine der drei Möglichkeiten. Bei 6 sind es 1 + 2 + 3 = 6, die Zahl trifft sich selbst – sie heißt vollkommen. Bei 12 sind es 1 + 2 + 3 + 4 + 6 = 16 und damit mehr, das nennt man abundant. Bei 8 sind es 1 + 2 + 4 = 7 und damit weniger, das heißt defizient. Jede Primzahl ist zwangsläufig defizient, weil ihr einziger echter Teiler die 1 ist.
Vollkommene Zahlen sind ausgesprochen selten: 6, 28, 496, 8.128 und dann erst wieder 33.550.336. Euklid zeigte, dass 2p−1 · (2p − 1) immer vollkommen ist, wenn 2p − 1 eine Primzahl ist – und Euler bewies gut 2.000 Jahre später, dass jede gerade vollkommene Zahl diese Form hat. Ob es überhaupt eine ungerade vollkommene Zahl gibt, ist bis heute offen und eines der ältesten ungelösten Probleme der Mathematik.
Wozu das im Alltag gut ist
In der Schule braucht man die Zerlegung, um Brüche zu kürzen und den Hauptnenner zu finden: Der größte gemeinsame Teiler ist das Produkt der gemeinsamen Primfaktoren in ihrer jeweils kleinsten Potenz, das kleinste gemeinsame Vielfache das Produkt aller vorkommenden Primfaktoren in ihrer höchsten. Wer beide Zerlegungen vor sich hat, sieht ggT und kgV sofort.
Außerhalb der Schule trägt die Primfaktorzerlegung die halbe digitale Welt. Das RSA-Verfahren, mit dem Bankverbindungen, Signaturen und ein großer Teil des Webverkehrs abgesichert werden, beruht darauf, dass die Multiplikation zweier großer Primzahlen mühelos ist und die Umkehrung praktisch unmöglich. Zwei Primzahlen mit je 300 Stellen sind in Sekundenbruchteilen multipliziert; das Produkt wieder zu zerlegen, übersteigt jede heute vorstellbare Rechenleistung.
Häufige Fragen
Wie mache ich eine Primfaktorzerlegung von Hand?
Schreibe die Zahl hin und teile sie durch die kleinste Primzahl, die ohne Rest aufgeht – also zuerst so oft wie möglich durch 2, dann durch 3, dann 5, 7, 11 und so weiter. Notiere jeden Teiler an den Rand. Sobald 1 herauskommt, bist du fertig, und die notierten Teiler sind die Zerlegung. Beispiel 360: 360÷2 = 180, 180÷2 = 90, 90÷2 = 45, 45÷3 = 15, 15÷3 = 5, 5÷5 = 1 – also 2³ · 3² · 5. Der Rechner oben zeigt diese Kette komplett an.
Ist 1 eine Primzahl?
Nein. Eine Primzahl muss genau zwei verschiedene Teiler haben, die 1 und sich selbst. Die 1 hat nur einen einzigen Teiler und fällt damit durch. Der eigentliche Grund für diese Festlegung ist die Eindeutigkeit der Zerlegung: Wäre 1 prim, ließe sich an jede Zerlegung beliebig oft eine 1 anhängen, und der Fundamentalsatz der Arithmetik wäre hinfällig.
Welche Zahl ist die größte bekannte Primzahl?
Die größten bekannten Primzahlen sind sogenannte Mersenne-Primzahlen der Form 2p − 1. Sie werden seit 1996 im verteilten Rechenprojekt GIMPS gesucht, an dem sich jeder mit seinem eigenen Computer beteiligen kann, und haben inzwischen deutlich über vierzig Millionen Stellen. Ausgedruckt füllt eine solche Zahl mehrere zehntausend Buchseiten. Für den praktischen Einsatz in der Verschlüsselung reichen dagegen Primzahlen mit ein paar hundert Stellen.
Warum findet der Rechner ab einer Billion nichts mehr?
Die Probedivision braucht im schlechtesten Fall so viele Schritte wie die Wurzel der Zahl. Bei einer Billion sind das eine Million Versuche, die der Browser in Sekundenbruchteilen erledigt. Bei einer Trillion wären es schon eine Milliarde, und die Seite würde einfrieren. Für größere Zahlen nutzt man deshalb andere Verfahren: den Miller-Rabin-Test für die reine Primzahlfrage und Pollard-Rho oder das Zahlkörpersieb für die Zerlegung.
Wie hängen ggT und kgV mit den Primfaktoren zusammen?
Zerlege beide Zahlen. Der größte gemeinsame Teiler ist das Produkt aller Primfaktoren, die in beiden vorkommen, jeweils mit dem kleineren Exponenten. Das kleinste gemeinsame Vielfache ist das Produkt aller vorkommenden Primfaktoren, jeweils mit dem größeren Exponenten. Für 60 = 2²·3·5 und 72 = 2³·3² ergibt das ggT = 2²·3 = 12 und kgV = 2³·3²·5 = 360. Es gilt immer ggT × kgV = a × b.
Was sagt die Eulersche Phi-Funktion aus?
φ(n) zählt, wie viele der Zahlen von 1 bis n keinen gemeinsamen Teiler mit n haben außer der 1. Für eine Primzahl p ist das trivial: alle p−1 Vorgänger sind teilerfremd. Für zusammengesetzte Zahlen fällt der Wert deutlich kleiner aus – bei 360 sind es nur 96 von 360. Die Funktion ist der Kern des RSA-Verfahrens und taucht überall dort auf, wo mit Resten gerechnet wird.
Quellen
- Euklid: Elemente, Buch VII bis IX – Fundamentalsatz der Arithmetik, Beweis der Unendlichkeit der Primzahlen und die Formel für gerade vollkommene Zahlen.
- Leonhard Euler: Beweis, dass jede gerade vollkommene Zahl die von Euklid angegebene Form hat, sowie Einführung der Phi-Funktion.
- DIN 1333 – Zahlenangaben; ISO 80000-2 – mathematische Zeichen und Symbole für die verwendete Notation.
- Bundesamt für Sicherheit in der Informationstechnik, Technische Richtlinie TR-02102-1 zu kryptographischen Verfahren und empfohlenen Schlüssellängen.
- Alle Tabellenwerte dieser Seite stammen aus Durchläufen des Rechners auf dieser Seite.
Mehr aus dieser Kategorie: Mathe-Rechner: Prozent, Bruch & Geometrie
Auch beliebt: Promillerechner · Schlafrechner · Hundejahre-Rechner
Entdecke das komplette Rechner-Portal auf rechnido – kostenlos und ohne Anmeldung.