Primfaktorzerlegung

Bei der Primfaktorzerlegung wird eine positive ganze Zahl als Produkt von Primzahlen geschrieben. Jede Zahl größer als 1 hat genau eine solche Zerlegung, unabhängig von der Reihenfolge der Faktoren. Zum Beispiel ist 360 = 2³ × 3² × 5. Der Rechner zeigt zusätzlich Teileranzahl und Teilersumme.

1 ist weder eine Primzahl noch eine zusammengesetzte Zahl. Nach Konvention gilt 1 als leeres Produkt ohne Primfaktoren. Dadurch bleibt der Fundamentalsatz der Arithmetik eindeutig: Jede Zahl größer als 1 besitzt genau eine Primfaktorzerlegung. Der Rechner gibt deshalb für 1, 0 und negative Zahlen kein Ergebnis aus.

Der Rechner verwendet Probedivision mit BigInt-Arithmetik, damit Zwischenwerte nahe der Eingabegrenze exakt bleiben. Zuerst prüft er die kleinen Primzahlen 2, 3, 5, 7 und 11. Danach testet er ungerade Teiler ab 13 und stoppt, sobald der Teiler größer als die Quadratwurzel des verbleibenden Werts ist.

Für n = p₁^e₁ × p₂^e₂ × ... ist die Teileranzahl das Produkt der Werte eᵢ + 1. Die Teilersumme ergibt sich aus dem Produkt der geometrischen Summen (p^(e + 1) - 1) ÷ (p - 1). Für 12 = 2² × 3 gibt es 6 positive Teiler, deren Summe 28 beträgt.

Die größte Eingabe ist 1.000.000.000.000, also 10¹². Diese Grenze hält die Probedivision auch auf mobilen Geräten schnell. Für diese Zahl beträgt die Quadratwurzel 1.000.000, und der Rechner prüft nur ungerade Kandidaten. Sehr große kryptografische Primfaktoren brauchen andere Verfahren wie den allgemeinen Zahlkörpersieb.