Primfaktorzerlegung Berechnen: So Geht's

Die Primfaktorzerlegung schreibt eine Zahl als Produkt von Primzahlen, also von Zahlen, die nur durch 1 und sich selbst teilbar sind. 360 zum Beispiel zerlegt sich in 2 × 2 × 2 × 3 × 3 × 5, kurz 2³ × 3² × 5. Man braucht das, um Brüche zu kürzen, den ggT oder das kgV zweier Zahlen zu finden, Wurzeln zu vereinfachen oder einfach zu prüfen, ob eine Zahl prim ist. Jede ganze Zahl größer als 1 hat dabei genau eine solche Zerlegung, das ist der Hauptsatz der Arithmetik, und er ist der Grund, warum das Verfahren überhaupt zuverlässig funktioniert.

Probedivision von Hand

Die Probedivision ist die direkteste Methode, um eine Zahl in ihre Primfaktoren zu zerlegen. Man teilt so lange durch die kleinstmögliche Primzahl wie möglich, bis nichts mehr aufgeht, wechselt dann zur nächsten Primzahl und macht so weiter, bis am Ende die 1 übrig bleibt.

Am Beispiel von 360:

1. Teste 2. 360 ist gerade, also teilt 2. 360 ÷ 2 = 180.
2. Teste 2 wieder. 180 ist ebenfalls gerade. 180 ÷ 2 = 90.
3. Teste 2 ein drittes Mal. 90 ÷ 2 = 45. Jetzt ist 45 ungerade, die 2 geht also nicht mehr auf. Die 2 kam insgesamt dreimal vor.
4. Wechsle zu 3. 45 ÷ 3 = 15.
5. Teste 3 wieder. 15 ÷ 3 = 5. Die 3 kam zweimal vor.
6. Teste 3 erneut. 5 ist nicht durch 3 teilbar, also weiter zur nächsten Primzahl.
7. Teste 5. 5 ÷ 5 = 1. Sobald das Ergebnis 1 ist, ist die Zerlegung fertig.

Die Teilschritte in Tabellenform:

Schritt	Zahl vorher	Geteilt durch	Ergebnis
1	360	2	180
2	180	2	90
3	90	2	45
4	45	3	15
5	15	3	5
6	5	5	1

Gesammelt ergibt das 2 × 2 × 2 × 3 × 3 × 5, in Exponentenform 2³ × 3² × 5. Zur Probe rechnet man einfach zurück: 2³ = 8, 3² = 9, und 8 × 9 × 5 = 360. Stimmt die Rückrechnung, war die Zerlegung richtig.

Die Reihenfolge der Primzahlen, die man testet, ist immer dieselbe: 2, 3, 5, 7, 11, 13, 17 und so weiter. Bei einer geraden Zahl lohnt es sich, zuerst so oft wie möglich durch 2 zu teilen, danach kommt in der Praxis fast immer die 3 an die Reihe, weil Vielfache von 3 (Quersumme durch 3 teilbar) recht häufig sind.

Ein größeres Beispiel und ein Primzahltest

Bei größeren Zahlen läuft die Probedivision genauso, nur mit mehr Schritten. Aber es gibt eine wichtige Abkürzung: man muss nicht bis zur Hälfte der Zahl testen, sondern nur bis zur Quadratwurzel. Sobald der Testteiler größer wird als die Quadratwurzel der Zahl, kann kein weiterer Faktor mehr existieren, den man nicht schon gefunden hätte, und die Zahl (oder was von ihr übrig ist) ist prim.

Ein gutes Beispiel dafür ist die Frage: Ist 997 eine Primzahl?

Die Quadratwurzel von 997 liegt bei ungefähr 31,6. Das heißt, es reicht, alle Primzahlen bis 31 zu testen: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31.

• 997 ist ungerade, die 2 scheidet aus.
• Quersumme 9 + 9 + 7 = 25, nicht durch 3 teilbar.
• Endet nicht auf 0 oder 5, die 5 scheidet aus.
• 997 ÷ 7 = 142 Rest 3.
• 997 ÷ 11 = 90 Rest 7.
• 997 ÷ 13 = 76 Rest 9.
• 997 ÷ 17 = 58 Rest 11.
• 997 ÷ 19 = 52 Rest 9.
• 997 ÷ 23 = 43 Rest 8.
• 997 ÷ 29 = 34 Rest 11.
• 997 ÷ 31 = 32 Rest 5.

Keine dieser Primzahlen teilt 997 ohne Rest. Da 32² = 1024 bereits über 997 liegt, ist damit jeder mögliche Teiler ausgeschlossen. 997 ist eine Primzahl.

Zur Einordnung, wie sich verschiedene Zahlen verhalten:

Zahl	Zerlegung	Prim?
97	97	Ja
100	2² × 5²	Nein
360	2³ × 3² × 5	Nein
997	997	Ja
1024	2¹⁰	Nein

1024 zeigt gut, wie eine Zahl fast ausschließlich aus einem einzigen Primfaktor bestehen kann: 2 hoch 10 ist 1024, ohne dass eine andere Primzahl überhaupt vorkommt.

Berechne mit deinen eigenen Zahlen

Bei größeren Zahlen wird das Testen jeder Primzahl bis zur Quadratwurzel schnell mühsam, vor allem wenn eine Zahl mehrere unhandliche Faktoren wie 17 oder 23 hat. Der Rechner unten übernimmt die Probedivision automatisch und zeigt die Zerlegung in Exponentenform, alle Teiler und ob die Zahl prim ist.

Primfaktorzerlegung-Rechner

Kostenlos, ohne Anmeldung, auf jedem Gerät.

Vollständiges Tool öffnen

Praktische Anwendungen

Brüche mit gemeinsamen Primfaktoren kürzen

Ein Bruch wie 84/126 lässt sich am saubersten über die Primfaktorzerlegung beider Zahlen kürzen. 84 zerlegt sich in 2² × 3 × 7, 126 zerlegt sich in 2 × 3² × 7. Die gemeinsamen Faktoren sind einmal 2, einmal 3 und einmal 7, also 2 × 3 × 7 = 42.

Teilt man Zähler und Nenner durch diese 42, bleibt 84 ÷ 42 = 2 und 126 ÷ 42 = 3 übrig. Der gekürzte Bruch ist 2/3, und weil kein gemeinsamer Primfaktor mehr übrig ist, lässt er sich nicht weiter vereinfachen. Der Vorteil gegenüber dem Ausprobieren einzelner Teiler: man sieht auf einen Blick, welche Faktoren wirklich gemeinsam sind, statt zufällig durch 2, dann durch 3, dann vielleicht noch durch 7 zu teilen und am Ende nicht sicher zu sein, ob wirklich vollständig gekürzt wurde.

Große Primzahlen als Basis der Kryptografie

Die Primfaktorzerlegung von 360 dauert mit Stift und Papier eine Minute. Genau dieser Unterschied zwischen leicht und schwer ist die Grundlage von RSA-Verschlüsselung, einem der meistgenutzten Public-Key-Verfahren im Internet.

Bei RSA wählt man zwei sehr große Primzahlen, oft mit hunderten Stellen, und multipliziert sie zu einer Zahl n. Diese Multiplikation ist für einen Computer trivial und dauert Millisekunden. Der umgekehrte Weg, aus n wieder die beiden ursprünglichen Primfaktoren zu finden, ist dagegen mit den heute bekannten Verfahren praktisch unmöglich, selbst mit sehr viel Rechenleistung dauert das Jahre bis Jahrtausende. Diese Einbahnstraße, leicht multiplizieren, schwer faktorisieren, macht n zur öffentlichen Zahl, die jeder kennen darf, während die beiden Primfaktoren selbst geheim bleiben und den privaten Schlüssel bilden. Genau deswegen bleibt jede Nachricht, die mit dem öffentlichen Schlüssel verschlüsselt wurde, ohne Kenntnis der beiden Primfaktoren praktisch unlesbar.

Häufige Fehler und Grenzfälle

0 und 1 sind weder prim noch zusammengesetzt. Eine Primzahl braucht per Definition genau zwei Teiler, 1 und sich selbst. Die 1 hat aber nur einen Teiler, sich selbst, und fällt damit aus der Definition heraus. Die 0 ist noch spezieller: sie ist durch jede ganze Zahl ohne Rest teilbar, hat also unendlich viele Teiler und keine sinnvolle Primfaktorzerlegung.

Negative Zahlen verwenden den Betrag. Bei minus 360 ist die Zerlegung dieselbe wie bei 360, nämlich 2³ × 3² × 5. Das Vorzeichen selbst ist kein Faktor der Zerlegung, es wird einfach beiseitegelassen und am Ende bei Bedarf wieder angehängt.

Wann man mit der Probedivision aufhören kann. Das ist der Fehler, der am meisten Zeit kostet: viele testen viel zu lange weiter, obwohl die Zahl längst als prim feststeht. Die Regel ist einfach: sobald das Quadrat des aktuellen Testteilers größer wird als der verbliebene Rest, ist dieser Rest selbst eine Primzahl, und man kann aufhören. Bei 89 zum Beispiel reicht es, 2, 3, 5 und 7 zu testen. Keine davon teilt 89, und da 11 hoch 2 gleich 121 schon über 89 liegt, steht fest, dass 89 prim ist, ohne dass man bis 88 weiterprobieren müsste.

Häufig gestellte Fragen

Wofür braucht man Primfaktorzerlegung überhaupt? Am häufigsten zum Kürzen von Brüchen, zum Berechnen von ggT und kgV, zum Vereinfachen von Wurzeln und zum Prüfen, ob eine Zahl prim ist. In der Informatik steckt sie außerdem hinter Verschlüsselungsverfahren wie RSA, die auf der Schwierigkeit beruhen, große Zahlen wieder in ihre Primfaktoren zu zerlegen.

Wie erkenne ich, ob eine Zahl prim ist, nur durch Hinsehen? Ein paar schnelle Filter helfen: gerade Zahlen außer der 2 sind nie prim, Zahlen, deren Quersumme durch 3 teilbar ist, auch nicht, und Zahlen, die auf 0 oder 5 enden, ebenfalls nicht (außer der 5 selbst). Bleibt nach diesen drei Filtern noch eine Zahl übrig, muss man tatsächlich mit der Probedivision bis zur Quadratwurzel weitermachen, um sicher zu sein.

Was ist die größte Zahl, die ich von Hand zerlegen kann? Praktisch liegt die Grenze irgendwo zwischen fünf und sieben Stellen, je nachdem wie viel Geduld man mitbringt und wie viele größere Primfaktoren die Zahl hat. Der Rechner oben nimmt einem die Probedivision bis zur Quadratwurzel ab und verarbeitet Zahlen bis zu einer Billion in Sekundenbruchteilen.

Kann eine Zerlegung mehr als eine richtige Lösung haben? Nein. Der Hauptsatz der Arithmetik garantiert, dass jede ganze Zahl größer als 1 genau eine Primfaktorzerlegung besitzt, wenn man von der Reihenfolge der Faktoren absieht. Egal ob man bei der Probedivision mit 2 oder gedanklich anders anfängt, am Ende kommt immer dieselbe Kombination von Primfaktoren heraus.