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.

[Mo53]

@Michael II Vielen Dank dafür

[Mo53]

@Delphi.Narium ist echt sehr nett von dir, könntest du vielleicht nochmal kurz erläutern wie du genau die fibonacci überprüfung gemacht hast, ich kann das nicht ganz nachvollziehen.

[Michael II]

Zitat von Mo53:

@Delphi.Narium ist echt sehr nett von dir, könntest du vielleicht nochmal kurz erläutern wie du genau die fibonacci überprüfung gemacht hast, ich kann das nicht ganz nachvollziehen.

DelphiNarium berechnet für jede Zahl zahl jedesmal alle Fibonaccizahlen bis zu zahl gemäss der Definition
f[n] := f[n-1] + f[n-2] für alle n>=2
f[0]=0*, f[1]=1

(*Je nach Literatur gibt's ein 0-tes Glied f[0] oder nicht (dann wird mit f[1]=f[2]=1 begonnen). Es ist eine Glaubensfrage: Die Entwicklung der Fibonacci Reihe wird oft mit der Vermehrung von Kaninchen verglichen. Wer glaubt, dass aus 0 und 1 Kaninchen etwas Grosses entstehen kann, nimmt das 0-te Glied 0 dazu.)

Den Code könntest du noch vereinfachen:
1. Vor der zahl Schleife suchst du nach der kleinsten Fibo Zahl f, für welche gilt f >= LOWER_BORDER
2. In der Schleife prüfst du immer auf f=zahl. Wenn f=zahl gibst du "Fibo=TRUE" aus und berechnest mittels f[n] := f[n-1] + f[n-2] die nächstgrössere Fibozahl f.

Vorteil?
Du rechnest so die Fibo-Folge bis UPPER_BORDER insgesamt genau einmal durch.
Im Code von DelphiNarium rechnest du UPPER_BORDER-LOWER-BORDER+1 mal die Fibo-Folge von 0 bis zahl.

Und wie erwähnt: Primzahlzwillinge (3,5), (5,7), (11,13) werden mit diesem Code nicht erkant.

[Delphi.Narium]

Zitat von Michael II:

Und wie erwähnt: Primzahlzwillinge (3,5), (5,7), (11,13) werden mit diesem Code nicht erkant.

{edit]
Diese Aussage ist so falsch, da hab' ich mich ganz gewaltig geirrt
Es ist ja noch viel schlimmer:

Wenn man Primzahl am Anfang der For-Schleife mit 0 belegt, wird keine Primzahl mehr gefunden.

Die Repeat-Schleife wird beendet, wenn uebrig = 0. Teiler hat dann "irgendeinen" Wert. Ist dieser zufällig = zahl, so wird Primzahl = zahl und bleibt solange unverändert, bis "irgendwann" teiler mal wieder = zahl wird. Mit einer Primzahlberechnung hat das eher nichts zu tuen. Hab's halt aus dem ersten Post einfach mal so übernommen.
Primzahl enthält immer die zuletzt gefundene Primzahl.
[/edit]

Delphi-Quellcode:

    // Überprüfung ob Teil der Fibonacci-Folge:
    a := 0; // Damit fangen wir an.
    b := 1; // a und b sind die ersten beiden Zahlen zur Berechnung.
    c := 0; // c ist ein "Zwischenspeicher".

    // Die Schleife wird beendet, wenn zahl in die Fibonacci-Folge gehört (fib = true)
    // oder a >= zahl geworden ist. 
    while (a < zahl) and not fib do
    begin
      c := a + b; // Zwischenspeicher = Summe von a und b = nächste Zahl für die Fibonacci-Folge.
      a := b; // a wird nun b, da wir immer nur die beiden letzten Zahlen berücksichtigen müssen.
      b := c; // b wird nun der Zwischenspeicher zugewiesen = soeben ermitttelte Zahl für die Fibonacci-Folge,
              // damit enthalten a und b immer die beiden letzten Zahlen, 
              // deren Zugehörigkeit zur Fibonacci-Folge festgestellt wurde. 
      fib := c = zahl; // Stimmen c und zahl überein, so gehört Zahl in die Fibonacci-Folge.
      fib := b = zahl; // Auf b = zahl abzufragen, wäre hier auch korrekt.
    end;

Code:

1. Schleifendurchlauf
c := 0 + 1  // a = 0 plus b = 1
a := 1 // a := b, b = 1
b := 1 // b := c, c = 1

2. Schleifendurchlauf
c := 1 + 1 // a = 1 plus b = 1
a := 1 // a := b, b = 1
b := 2 // b := c, c = 2

3. Schleifendurchlauf
c := 1 + 2 // a = 1 plus b = 2
a := 2 // a := b, b = 2
b := 3 // b := c, c = 3

4. Schleifendurchlauf
c := 2 + 3 // a = 2 plus b = 3
a := 3 // a := b, b = 3
b := 5 // b := c, c = 5

5. Schleifendurchlauf
c := 3 + 5 // a = 3 plus b = 5
a := 5 // a := b, b = 5
b := 8 // b := c, c = 8

6. Schleifendurchlauf
c := 5 + 8 // a = 5 plus b = 8
a := 8 // a := b, b = 8
b := 13 // b := c, c = 13

7. Schleifendurchlauf
c := 8 + 13 // a = 8 plus b = 3
a := 13 // a := b, b = 13
b := 21 // b := c, c = 21

8. Schleifendurchlauf
c := 13 + 21 // a = 13 plus b = 21
a := 21 // a := b, b = 21
b := 34 // b := c, c = 34

9. Schleifendurchlauf
c := 21 + 34 // a = 21 plus b = 34
a := 34 // a := b, b = 34
b := 55 // b := c, c = 55

[Mo53]

@Michael II Es tut mir leid für meine Dummheit aber ich verstehe deinen Lösungsvorschlag für die Primzahlen nach mehrmaligem durchlesen immer noch nicht.
Könntest du den Lösungsansatz vielleicht step by step erklären.

[Michael II]

Zitat von Mo53:

@Michael II Es tut mir leid für meine Dummheit aber ich verstehe deinen Lösungsvorschlag für die Primzahlen nach mehrmaligem durchlesen immer noch nicht.
Könntest du den Lösungsansatz vielleicht step by step erklären.

Für zahl = 2 gibst du prim aus.

Du fragt wegen allen anderen Primzahlen. Hier Code.

Delphi-Quellcode:

var teiler, pruefebis, zahl : integer;
    ist_prim : boolean;
....

  zahl := 91;

  ist_prim := true;
  teiler := 3;
  pruefebis := trunc(sqrt(zahl));
  while ist_prim and ( teiler <= pruefebis ) do
  begin
    ist_prim := zahl mod teiler <> 0;
    inc( teiler, 2 ); // teiler := teiler + 2;
  end;

Lade den Code in der IDE und steppe durch wie TurboMagic geschrieben hat.

Zum Code:

Wir nehmen zuerst ist_prim:= TRUE an und werden vielleicht später (in der while Schleife) das Gegenteil beweisen.

zahl ist im Beispiel 91.
Du weisst, dass es einen echten Teiler von 91 <= sqrt(91) geben muss, wenn 91 nicht prim ist.
Wir prüfen also für teiler mit den Werten 3,5,...9, ob zahl durch teiler teilbar ist.
Wenn dem so ist, wird ist_prim in der while Schleife FALSE. => Die Schleife wird wegen der Abbruchbedingung (while ist_prim and ( teiler <= pruefebis ) do) verlassen.

Am Ende der while Schleife ist ist_prim TRUE, wenn zahl eine Primzahl ist, sonst FALSE



Da ihr wahrscheinlich keine "function" benutzen dürft, ist die Aufgabe mit den Primzahlzwillingen etwas aufwändig [und ohne die Verwendung von "function" vielleicht auch ein wenig nutzlos ].

[Mo53]

@Michael II ist es möglich das ganze auch in einer repeat schleife zu verpacken?
Wie mach man das jetzt mit dem Primzahlzwilling, da istprime ja boolean ist klappt es in der nächsten überprüfung nichtmehr mit zahl+2 = istprime

[Michael II]

Dieser Code gibt dir aus, ob eine Zahl gerade ist, ob fibo, ob prim, ob zwillingsprim.

Da du sicher keine function istprim(zahl) verwenden darfst, merken wir uns halt in zwei booleschen Variablen, ob die letzte ungerade Zahl (zahl-2) prim war (letzte_warprim) und ob die nächste ungerade (zahl+2) es sein wird (naechste_istprim). So müssen wir jede zahl nur einmal auf prim prüfen.

Die "Spezialwerte" 0,1,2 geben wir direkt aus. (Man müsste den Code durch diese drei "Sonderfälle" aufblähen. - Tun wir nicht.)

Was macht das Programm?

Fibo: Für fibo berechnen wir am Anfang die kleinste Fibo-Zahl f, welche >= LOWER_BORDER ist. Dann geht's ab in die while Schleife. Sobald zahl=f wissen wir "fibo!". Wir setzen im fibo Fall istfibo:=TRUE und müssen das nächste Glied f der Fibofolge berechnen. Bei der Berechnung von f=f[n] greifen wir auf die gespeicherten Werte von f[n-1] und f[n-2] zurück.

Gerade: istgerade := zahl mod 2 = 0; und das war's bereits.

Primzahlen und deren Zwillinge: Für Zahlen, welche ungerade sind, prüfen wir auf prim. Wir prüfen dabei nicht die aktuelle Zahl, sondern "zahl+2". Grund: Wir müssen für die Bewertung "zahl ist Zwilling oder nicht" wissen, ob die nächste ungerade Zahl "zahl+2" prim ist. Wir speichern in naechste_istprim ab, ob "zahl+2" prim ist. In letzte_warprim merken wir uns, ob die letzte ungerade Zahl prim war. In diese_istprim steht, ob zahl prim ist. diese_istprim berechnen wir dabei nicht via Faktorzerlegung von zahl: Wir wissen ja dank letzte_warprim, ob zahl prim ist oder nicht. "zahl" ist Teil eines Primzahlzwillings, wenn
primzwilling := diese_istprim and ( letzte_warprim or naechste_istprim );

Fertig - Viel Spass beim Denken.

Delphi-Quellcode:

var teiler, sqrt_n, naechste, zahl, fn_1, fn_2, f : int64;
    primzwilling, istfibo, istgerade, letzte_warprim, naechste_istprim, diese_istprim : boolean;

const
  LOWER_BORDER = 0;
  UPPER_BORDER = 50;

begin
  if ( LOWER_BORDER = 0 ) then writeln( '0 even: TRUE fib: TRUE prim: FALSE twinprim: FALSE' );
  if ( LOWER_BORDER <= 1 ) and ( 1 <= UPPER_BORDER ) then writeln( '1 even: FALSE fib: TRUE prim: FALSE twinprim: FALSE' );
  if ( LOWER_BORDER <= 2 ) and ( 2 <= UPPER_BORDER ) then writeln( '2 even: TRUE fib: TRUE prim: FALSE twinprim: FALSE' );
  if ( LOWER_BORDER mod 2 = 0 ) then zahl := LOWER_BORDER-3 else zahl := LOWER_BORDER-4;

  if ( zahl < 3 ) then
  begin
    zahl := 3;
    naechste_istprim := true; // 3 ist Primzahl
  end;

  fn_1 := 1;
  fn_2 := 1;
  f := 2;
  while ( f < zahl ) do // berechne die kleinste Fibo-Zahl f, welche >= LOWER_BORDER
  begin
    f := fn_1 + fn_2;
    fn_2 := fn_1;
    fn_1 := f;
  end;

  while ( zahl <= UPPER_BORDER ) do
  begin
    istfibo := f = zahl;
    if istfibo then 
    begin // die nächste Fibozahl wird berechnet
        f := fn_1 + fn_2;
        fn_2 := fn_1;
        fn_1 := f;
    end;

    istgerade := zahl mod 2 = 0;

    if not istgerade then
    begin
      diese_istprim := naechste_istprim; // in durchlauf "zahl-2" haben wir berechnet, ob "zahl" prim ist
      naechste := zahl + 2; // die nächste ungerade zahl nach "zahl" auf prim prüfen
      sqrt_n := trunc(sqrt(naechste)); // bis zu diesem wert suchen wir nach möglichen teilern von naechste
      teiler := 3;
      naechste_istprim := true; // wir nehmen mal an, "naechste" sei prim
      while naechste_istprim and ( teiler <= sqrt_n ) do
      begin // und prüfen, ob dem so ist
        naechste_istprim := naechste mod teiler <> 0;
        inc( teiler, 2 );
      end; 
      // naechste_istprim = true, wenn naechste=zahl+2 prim ist
      // wir prüfen, ob "zahl" zu einem Zwilling gehört
      primzwilling := diese_istprim and ( letzte_warprim or naechste_istprim );
      letzte_warprim := diese_istprim; // wir merken uns für runde "zahl+2", ob "zahl" prim ist
    end
    else
    begin
      diese_istprim := false; // "zahl" ist gerade also nicht prim
      primzwilling := false;  // ..und damit auch nicht Teil eines Zwillings
    end;

    if ( zahl >= LOWER_BORDER ) then // Ausgabe
    writeln(zahl, ' even: ', istgerade, ' fib: ', istfibo, ' prim: ', diese_istprim, ' twinprim: ', primzwilling );
    inc( zahl );
  end;

  readln;