Primfaktorzerlegungsrechner Finden Sie die Primfaktoren jeder Zahl mit erweiterter Form und Teileranzahl.

Der Algorithmus verwendet eine Teilungsprüfung: Beginnend mit der kleinsten Primzahl (2) wird die Zahl so lange geteilt, wie sie teilbar ist, und der Exponent wird gezählt. Dann geht man zum nächsten potenziellen Faktor über (3, 4, 5, ...). Wir müssen nur bis zur Quadratwurzel von n testen, da, wenn n einen Faktor größer als die Quadratwurzel von n hat, der entsprechende Kofaktor kleiner als die Quadratwurzel von n sein muss und bereits gefunden worden wäre. Nach der Schleife ist die verbleibende Zahl, wenn sie größer als 1 ist, selbst ein Primfaktor. Die Zeitkomplexität beträgt O(√n) im Worst-Case-Szenario (wenn n eine Primzahl ist). Die Formel für die Anzahl der Teiler leitet sich aus der multiplikativen Natur der Teilerfunktion ab: Jede Potenz einer Primzahl p^a trägt (a+1) Auswahlmöglichkeiten (p^0, p^1, ..., p^a) bei, wenn man Teiler aufbaut, und diese Auswahlmöglichkeiten sind unabhängig voneinander für verschiedene Primzahlen, sodass die Gesamtzahl das Produkt von (aᵢ+1) für alle Primfaktoren ist. Zum Beispiel hat 360 = 2³ × 3² × 5¹ (3+1)(2+1)(1+1) = 24 Teiler.