Erstellung einer Schleife mit drei Überprüfungen

[Michael II]

Zitat von Mo53:

@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.