Programme	Addition Lineare Gleichung Sieb des Eratosthenes Plotter Pfad: Startseite / Fächer / Informatik / Delphi / Programme / Sieb des Eratosthenes
Autor: mk 18.10.2005 19:15:34 16377	Sieb des Eratosthenes

Das Sieb des Eratosthenes

Im Mathematik-Lehrbuch der 6.Klasse (Lambacher-Schweizer 6, Klett-Verlag, 73102) findet man folgende Beschreibung:

1. Schreibe die Zahlen von 2 bis z.B. 100 auf.
2. Die erste Zahl ist 2. Streiche alle Vielfachen von 2, außer 2 selbst.
3. Suche die nächste nicht gestrichene Zahl; streiche alle Vielfachen von ihr, außer der Zahl selbst.
4. Wiederhole 3., so lange man auf diese Art noch Vielfache streichen kann.

Alle übrig gebliebenen Zahlen sind die Primzahlen. Bei den Zahlen bis 100 kann man schon nach dem Streichen aller Vielfachen von 7 aufhören.

Aufgabe

Schreibe ein Delphi-Programm, das nach obigem Algorithmus Primzahlen sucht.

mögliche Schritte hin zur Lösung

• Der Algorithmus wird mit kleinen Zahlen (vielleicht bis 20) mit Papier und Bleistift durchgeführt. Auf diese Weise testet man, ob er hinreichend verstanden ist.
• Es wird überlegt, wie man die 'Wirklichkeit' in den Computer abbilden kann. Hier z.B.: Wie schreibt man die Zahlen 2 bis 100 auf?
• zahl : array[2..100] of integer; scheint eine passende Datenstruktur zu sein.
• Das Aufschreiben könnte mit for i := 2 to 100 do zahl[i] := i; erledigt werden.
• Wie könnte man das Streichen der Zahl 12 realisieren? Z.B. mit zahl[12] := 0;
• Beim Streichen der Vielfachen weiß man nicht vorher, wie oft man streichen muss. Ein typischer Fall für eine while-Schleife. Hier muss man sich Gedanken über die Abbruchbedingung machen.

  // es werden die Vielfachen von a getrichen
  v := 2; // v gibt die 'Vielfachheit' an
  while v*a <= 100 do
  begin
    zahl[v*a] := 0;
    v := v+1;
  end;
  

• Wie findet man die nächste nicht gestrichene Zahl? Es fällt auf, dass man sich irgendwie merken muss, welches die letzte gefundene Zahl ist. Da diese Zahl eine Primzahl ist, scheint p : integer; eine passende Vereinbarung zu sein. Wir führen einen Zeiger, einen Index i : integer ein und setzen den Zeiger auf p+1 (i := p+1;). Dann rücken wir den Zeiger so oft weiter, bis wir eine nicht gestrichene Zahl gefunden haben.

  i := p+1;
  while zahl[i] = 0 do i := i + 1;
  

  Was ist aber, wenn schon alle Zahlen gestrichen sind? Dann läuft der Zeiger über die vereinbarte Feldgrenze hinweg.

  i := p+1;
  while (i<=100) and (zahl[i] = 0) do i := i + 1;
  

  Obige Lösung führt zu einem Abbruch, wenn i > 100 geworden ist. Dann sollte man aber nicht zahl[i] auswerten, da diese Stelle nicht mehr im Array, im Feld ist. In Delphi werden je nach Einstellung logische Ausdrücke von links nach rechts ausgewertet und die Auswertung abgebrochen, wenn das Ergebnis schon feststeht (Kurzschlussverfahren).
• Man wird versuchen, obige Teilüberlegungen zusammenzufassen, etwa:

    for i := 2 to 100 do zahl[i] := i;
    p := 2;
    while p <= 100 do
    begin
      // es werden die Vielfachen von p getrichen
      v := 2; // v gibt die 'Vielfachheit' an
      while v*p <= 100 do
      begin
        zahl[v*p] := 0;
        v := v+1;
      end;
      // es wird die nächste nicht gestrichene Zahl gesucht
      i := p+1;
      while (i<=100) and (zahl[i] = 0) do i := i + 1;
      // die gefundene Zahl ist eine Primzahl oder zu groß
      p := i;
    end;
  

• Es ist sinnvoll, den Algorithmus formal in der vertrauten Programmiersprache zu beschreiben, da so natürlich schnell erste Tests möglich sind.
• Oft wird man eine Memo-Komponente (z.B. mAusgabe) als 'Ausgabe-Bildschirm' gebrauchen und Zeilen mit mAusgabe.Lines.Add(...) ausgeben.
• Bis zu einer lauffähigen ersten Lösung sind vermutlich fehlende Vereinbarungen zu ergänzen und einige Syntax-Fehler zu beseitigen.
• Läuft das Programm. so wird man ausgiebige Tests machen. In unserem Fall, kannman sich die Primzahlen bis 100 auch anders beschaffen und mit der Programm-Ausgabe vergleichen.

Erste vorläufige Lösung

eratosthenes0.zip

Kritik der Lösung

Es ist typisch, dass man bei der ersten Lösung in Teillösungen gedacht hat und nicht mehr einen klaren Blick für das Ganze hat. Hier sollte man kritisch über die Lösung sehen. Sind die Variablen sinnvoll benannt? Sind die Datentypen sinnvoll gewählt? Braucht man überhaupt alle Variablen oder sind Reste früherer Versuche im Programm-Code enthalten? Wurden Programmiersprachen-abhängige Besonderheiten benutzt?

Folgende Version ist an einigen Stellen verändert. Was bewirken die Änderungen? Ist das Programm 'besser'?

procedure TForm1.bRechneClick(Sender: TObject);
const
  n = 200;
var
  zahl   : array[2..n] of boolean;
  p,i,v  : integer;
  weiter : boolean;
begin
  // Eingabe

  // Verarbeitung
  for i := 2 to n do zahl[i] := true;
  p := 2;
  while p <= n do
  begin
    // es werden die Vielfachen von p getrichen
    v := 2*p; // v ist das 'Vielfache'
    while v <= n do
    begin
      zahl[v] := false;
      v := v+p;
    end;
    // es wird die nächste nicht gestrichene Zahl gesucht
    p := p+1;
    if p <= n then weiter := true;  // 'weiter' ist ein logischer Schalter
    while weiter do
      if (p<=n) and (zahl[p] = false)
      then
        p := p+1
      else
        weiter := false;
  end;

Es folgt eine dritte Version:

  for i := 2 to n do zahl[i] := true;
  for i := 2 to n do
    if zahl[i] = true
    then
    begin
      // es werden die Vielfachen von zahl[i] getrichen
      v := 2*i;
      while v <= n do
      begin
        zahl[v] := false;
        v := v+i;
      end;
    end;

Diese Version entspricht nicht mehr 1:1 der Beschreibung aus dem Mathematikbuch. Wie müsste hier die Beschreibung lauten?

Aufgabe