@Michael II kannst du das vielleicht mehr erläutern ggf. mit einem beispiel
Falls du damit den Teil meinst bis sqrt(zahl) auf Teilbarkeit checken:
Jede Zahl lässt sich wie du weisst in Primfaktoren zerlegen oder eben nicht.
Du suchst mit deinem Test von 2 an aufwärts (bis zahl) nach einer Zahl p, welche echter Teiler von zahl ist.
Wenn es eine solche Zahl p < zahl gibt, dann kannst du zahl zerlegen in
zahl = p*q
Du weisst bei dieser Zerlegung, dass
q nicht kleiner als p sein kann. Grund: Du suchst ja von 2 aufwärts und bist
zuerst auf p gestossen. (Wäre q kleiner als p wärst du bei deiner Suche zuerst auf q gestossen.)
Es gilt also p <= q [Wichtig, dass du diesen Schluss begreifst.]
=> Bleibt zu überlegen, wie gross p maximal sein kann.
Da p kleiner als q ist, ist p im Fall p=q maximal =>
p <= sqrt(zahl)
Zahlenbeispiel?
Teste 41
Du prüfst momentan /2 /3 /4 /5 /6 /7 /8.... /41
Es reicht, nur /2 /3 /4 /5 /6 zu testen. Tests ab /7 lohnen sich nicht mehr, da wir oben gezeigt haben, dass der kleinste echte Teiler von zahl kleiner oder gleich sqrt(zahl) ist; also hier p <= sqrt(41) sein muss.
- Sobald du einen Teiler gefunden hast, kannst du deine Berechnung abbrechen und auf "nicht prim" entscheiden.
Du berechnest ja "übrig" - wenn dein "übrig=0" hast du einen Teiler von Zahl gefunden => Zahl ist nicht prim, Abbruch => Abbruchbedingung übrig=0.
Wie früher erwähnt: Wenn 2 nicht Teiler von Zahl ist, dann musst du die anderen geraden Zahlen 4,6,8,... nicht mehr checken. Grund: Bei deinem Test wärst du ja bereits bei /2 fündig geworden und hättest auf
nicht prim entschieden.