Zitat von
Khabarakh:
Zitat von
Antigo:
Bei der Faktorisierung ist das allerdings anders. Hier muss ich bis zur Hälfte durchgehen.
Ich gehe ja folgendermassen vor (Methode 2/Methode 3), dass ich die Zahl durch alle Zahlen teile und nach einem ganzzahligen Teiler suche (wiederum zahl mod i = 0). Habe ich einen gefunden, überprüfe ich ob dieser Teiler auch eine Primzahl ist, [...]
Wozu denn das
? Wenn du den zu testenden Teiler schrittweise erhöhst,
muss der erste Treffer auch eine Primzahl sein.
Ganz genau! Wenn du es nämlich so machst, wie ich es beschrieben hab, wird die Zahl, ja nie durch z.B. 4 teilbar sein. Wenn doch, wäre sie ja bereits bei der 2 geteilt worden und diese Zahl wird nicht weiter überprüft, sondern nur noch die Hälfte dieser Zahl (100 teilst du nie durch 4 sondern erst durch 2, dann hast du ja nur noch 50 und die lässt sich dann nicht mehr durch 4 teilen). Wenn man also (nach meinem Verfahren) einen möglichen Teiler findet, ist er immer eine Primzahl.