Sieb des Erathosthenes

[dolphin]

Hallo,

ich probiere seit ein paar Stunden das folgende WirWar zum laufen zu bringen...

Code:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Edit1: TEdit;
    Button1: TButton;
    ListBox1: TListBox;
    procedure Button1Click(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

var
  primes:TStringList;
  nr:Integer;
  i,j,n, luckynr: Integer;
begin
  primes:= TStringList.Create;
  nr:= strtoint(edit1.Text);
  for i:= 2 to nr do begin
    primes.Add(inttostr(i));
    end;

  //showmessage(primes[-1]);
  i:=0;
  n:= i+1;
  while True do begin
    j := strtoint(primes[n]);
    luckynr:=strtoint(primes[i]);

    if j = strtoint(primes[primes.count-1]) then begin

      if j mod luckynr = 0 then begin

        primes.Delete(primes.IndexOf(inttostr(j)));
        end;

      i:=i+1;
      n:=i+1;
      end

    else if j mod luckynr = 0 then begin
      primes.Delete(primes.IndexOf(inttostr(j)));
      n:=n+1
      end

    else if luckynr = strtoint(primes[primes.count-1]) then begin
      break;
      end

    else begin
      n:=n+1;
      end;

    end;



end;

end.

Er will mir einfach nicht richtig die Zahlen aus der TStringList streichen und nach einer Weile bekomme ich einen Fehler das ich ueber das Listenende waere. Ich benutze die TStringList weil dadurch die Elemente nachruecken wenn ich eines entferne was ja in einem Array nicht der fall ist.

Greetz
Dolphin

[Bummi]

Delphi-Quellcode:

var
  primes: TStringList;
  i, j, nr, curr: Integer;
begin
  primes := TStringList.Create;
  try
  nr := strtoint(Edit1.Text);
  for i := 2 to nr do
  begin
    primes.Add(inttostr(i));
  end;
  for i := 2 to nr do
      begin
        for j :=  primes.Count - 1 downto 0 do
          begin
              curr := StrToInt(primes[j]);
              if (curr <> i) and  (curr mod i = 0)  then
                begin
                   primes.Delete(j);
                end;
          end;
      end;

  Listbox1.Items.Assign(primes);
  finally
     primes.Free;
  end;
end;

oder gleich:

Delphi-Quellcode:

var
  primes: TStringList;
  i, j, nr, curri,currj: Integer;
begin
  primes := TStringList.Create;
  try
  nr := strtoint(Edit1.Text);
  for i := 2 to nr do
  begin
    primes.Add(inttostr(i));
  end;
  for i := primes.Count - 1 downto 0 do
      begin
        for j :=  primes.Count - 1 downto 0 do
          begin
              curri := StrToInt(primes[i]);
              currj := StrToInt(primes[j]);
              if (currj <> curri) and  (currj mod curri = 0)  then
                begin
                   primes.Delete(j);
                end;
          end;
      end;

  Listbox1.Items.Assign(primes);
  finally
     primes.Free;
  end;
end;

[Uwe Raabe]

Hier steckt schonmal ein Fehler:

Delphi-Quellcode:

    else if j mod luckynr = 0 then begin
      primes.Delete(primes.IndexOf(inttostr(j)));
      n:=n+1
      end

    else if luckynr = strtoint(primes[primes.count-1]) then begin

Das Delete löscht ja den aktuellen Eintrag. Dann darf das n nicht erhöht werden, sonst überspringst du einen Wert.

Im Übrigen überprüfst du die Abbruchkriterien zu spät, daher die Range-Fehler.

Weiterhin sind deine IndexOf-Aufrufe tödlich für die Performance. Wenn man berücksichtigt, daß j ja die Zahl an Stelle n in der StringList darstellt, dann gilt n = primes.IndexOf(inttostr(j)). Somit vereinfacht sich dein Code auf unter Berücksichtigung der Bereichsgrenzen auf:

Delphi-Quellcode:

  
  i := 0;
  { der letzte Eintrag braucht niemals überprüft zu werden }
  while i < primes.count - 1 do begin
    luckynr := strtoint(primes[i]);
    n := i + 1;
    while n < primes.Count do begin
      j := strtoint(primes[n]);
      if j mod luckynr = 0 then begin
        primes.Delete(n);
      end
      else begin
        n := n + 1;
      end;
    end;
    i := i + 1;
  end;

[Uwe Raabe]

Zitat von Bummi:

Delphi-Quellcode:

  for i := primes.Count - 1 downto 0 do
      begin
        for j :=  primes.Count - 1 downto 0 do
          begin
              curri := StrToInt(primes[i]);
              currj := StrToInt(primes[j]);
              if (currj <> curri) and  (currj mod curri = 0)  then
                begin
                   primes.Delete(j);
                end;
          end;
      end;

Das sind mir irgendwie viel zu viele Iterationen.

[Bummi]

@Uwe Raabe stimmt ...

[Uwe Raabe]

@Bummi, so als Beispiel wird bei N = 100 in deinem Fall die innere Schleife 8284x durchlaufen, während bei aufsteigendem Duchlauf nur 411 Durchläufe kommen. Der Grund liegt darin, daß bei rückwärtigem Durchlauf die niedrigen Primzahlen erst sehr spät zur Überprüfung kommen. Diese sorgen aber für eine größere Ausdünnung des Siebs.

[dolphin]

Hallo,

vielen Dank euch 2 fuer die fixe Antwort. Jetzt kann ich schauen was in meinem Code schief lief.

Ich hatte auch das Problem das ich mit .delete Strings aus der Liste loeschte sie aber in der naechsten Schleife wieder vorhanden waren. Woran liegt das?

[Bummi]

@Uwe Raabe ich weiß schon und habe es nach Deiner Antwort selbst getestet.
Ich kann meinen Beitrag löschen, oder als schlechtes Beispiel stehen lassen ....

[p80286]

Zitat von dolphin:

Ich hatte auch das Problem das ich mit .delete Strings aus der Liste loeschte sie aber in der naechsten Schleife wieder vorhanden waren. Woran liegt das?

da vermute ich, daß garnichts gelöscht wurde.
Hast Du einmal den Debugger bemüht?

Gruß
K-H