Faktorisierung

[Cöster]

Zitat von Antigo:

Am längsten dauern übrigens Primzahlen, da das Programm solange Teiler sucht, bis der Teiler den er ausprobiert größer ist als die Hälfte der Zahl.

Es reicht doch, wenn du so lange ausprobierst, bis der Teiler größer ist als die Wurzel der Zahl.

Beispiel:
Die Zahl lautet 53, Wurzel ist also zwischen 7 und 8. Du versuchst einfach 2, 3, 5, 7 (du solltest die unteren Primzahlen in einem Array speichern, damit du Zahlen wie 4 oder 6 gar nicht erst ausprobieren musst), die nächste Zahl wäre 11, liegt also über der Wurzel und du brauchst sie gar nicht mehr auszuprobieren, da der andere Teiler dann ja kleiner als die Wurzel wäre, aber die hast du ja schon alle ausprobiert.

Außerdem solltest du rekursiv rechnen (vielleicht machst du das ja auch schon). Dann müsstest du bei z.B. 100 nur 6 mal probieren:
100/2 -> 50
50/2 -> 25
25/2 -> geht nicht
25/3 -> geht nicht
25/5 -> 5 //jetzt nicht wieder die Zahlen kleiner als 5 ausprobieren, die hast du ja schon alle getestet
5/5 -> 1 fertig

Wenn du nach 100/2 allerdings weiterprobieren würdest mit 100/3, müsstest du wirklich bis 50 durchprobieren. Das bedeutete ein Vielfaches des Rechenaufwandes. Wie soll das dann erst bei größeren Zahlen sein?