Primfaktorzerlegung: Rechner mit Faktorbaum

So benutzt du den Rechner

Gib eine natürliche Zahl ab 2 ein. Der Rechner teilt sie so lange durch die kleinstmögliche Primzahl, bis 1 übrig bleibt, und zeigt jede Division. Am Ende fasst er gleiche Faktoren als Potenz zusammen: 360 = 2³ · 3² · 5. Darunter stehen die Anzahl und die Summe aller Teiler, die Teiler selbst und besondere Eigenschaften der Zahl.

Was ist eine Primfaktorzerlegung?

Jede natürliche Zahl größer als 1 ist entweder selbst eine Primzahl oder lässt sich als Produkt von Primzahlen schreiben. Diese Darstellung ist bis auf die Reihenfolge der Faktoren eindeutig. Das ist der Fundamentalsatz der Arithmetik, den schon Euklid in seinen „Elementen“ vorbereitete und Carl Friedrich Gauß 1801 vollständig bewies. Primzahlen sind damit so etwas wie die Atome der Zahlen.

Der Faktorbaum

Im Faktorbaum spaltest du von einer Zahl immer einen Faktor ab und schreibst beide Teile darunter. Zerfällt nichts mehr, steht unten eine Primzahl. Der Rechner spaltet stets die kleinste Primzahl ab, deshalb wächst sein Baum schräg nach rechts. Du darfst aber auch anders beginnen, etwa mit 360 = 36 · 10. Am Ende kommen immer dieselben Primfaktoren heraus.

Teiler aus der Zerlegung ablesen

Aus den Exponenten lässt sich die Anzahl der Teiler direkt berechnen: Man erhöht jeden Exponenten um 1 und multipliziert. Für 360 = 2³ · 3² · 5¹ sind das (3 + 1) · (2 + 1) · (1 + 1) = 24 Teiler. Jeder Teiler entsteht, indem man für jede Primzahl einen Exponenten zwischen 0 und dem Höchstwert wählt. Mit der Zerlegung bestimmst du auch schnell den ggT und das kgV mehrerer Zahlen, dafür gibt es den ggT- und kgV-Rechner.

Erweitert: sehr große Zahlen

Für kleine Zahlen reicht das Ausprobieren aller Primzahlen bis zur Wurzel. Bei Zahlen mit 20 oder 30 Stellen würde das Jahre dauern. Der Rechner nutzt deshalb zwei moderne Verfahren: den Miller-Rabin-Test, der in Sekundenbruchteilen erkennt, ob eine Zahl prim ist, und den Pollard-Rho-Algorithmus, der große Faktoren findet. So zerlegt er etwa 2⁶⁴ + 1 = 274 177 · 67 280 421 310 721. Dass sehr große Zahlen schwer zu zerlegen sind, ist übrigens die Grundlage der RSA-Verschlüsselung im Internet.

Häufige Fragen