Primfaktorzerlegung-Rechner

Eine Zahl in Primzahlen zerlegen

Jede ganze Zahl größer als 1 lässt sich – abgesehen von der Reihenfolge der Faktoren – auf genau eine Weise als Produkt von Primzahlen schreiben. Das ist der Fundamentalsatz der Arithmetik, und die Primfaktorzerlegung einer Zahl ist genau dieses eindeutige Produkt. Zum Beispiel 360 = 2³ × 3² × 5. Dieser Rechner bestimmt die Zerlegung jeder ganzen Zahl bis 9,007,199,254,740,991, also 2^53 − 1 und damit die größte ganze Zahl, die ein Browser exakt darstellen kann. Die Ergebnisse erscheinen in Exponentenform, in vollständig ausgeschriebener Form und als Faktorbaum.

Teiler, ihre Anzahl und ihre Summe

Sobald die Primfaktorzerlegung bekannt ist, ergeben sich viele weitere Eigenschaften unmittelbar. Ist eine Zahl gleich p₁^a₁ × p₂^a₂ × …, dann beträgt die Anzahl der positiven Teiler (a₁ + 1)(a₂ + 1)…, weil jeder Teiler für jede Primzahl einen Exponenten von 0 bis zur vollen Potenz wählt. Die Teilersumme ist das Produkt von (1 + p + p² + … + p^a) über alle Primzahlen. Für 360 ergibt das 4 × 3 × 2 = 24 Teiler mit der Summe 1170. Das Werkzeug listet alle Teiler in aufsteigender Reihenfolge auf, was bei Aufgaben wie dem Finden gemeinsamer Teiler, dem Kürzen von Brüchen und der Prüfung hilft, ob eine Zahl vollkommen ist, das heißt, ob ihre Teiler außer ihr selbst zusammen die Zahl ergeben.

Wie die Zerlegung funktioniert

Kleine Primfaktoren werden per Probedivision mit einem Rad entfernt, das Vielfache von 2 und 3 überspringt. Was übrig bleibt, hat nur große Primfaktoren; der Rechner prüft diesen Rest daher mit einem deterministischen Miller-Rabin-Test, und ist er zusammengesetzt, wird er mit Pollard's rho-Algorithmus unter Verwendung exakter BigInt-Arithmetik gespalten und anschließend rekursiv weiter zerlegt. So liefern selbst Produkte zweier Primzahlen im zweistelligen Millionenbereich schnell ein Ergebnis, wo reine Probedivision langsam wäre. Der Faktorbaum zeigt einen Weg zu den Primzahlen, indem in jedem Schritt die kleinste Primzahl abgespalten wird.

Im Stapelmodus können Sie eine ganze Liste von Zahlen einfügen und erhalten eine Tabelle mit jeder Zerlegung und der Teileranzahl, wobei ungültige Einträge einzeln markiert werden, statt den Durchlauf abzubrechen. Alles wird in Ihrem Browser berechnet, sodass die eingegebenen Zahlen niemals hochgeladen werden.