Sehr schneller Primzahl-Finder

[GTA-Place]

Auch euch will ich meinen Source nicht vorbehalten:

Delphi-Quellcode:

function Prim(Zahl: Cardinal): Boolean;  
var  
  Teiler: PCardinal;  
  Wurzel: Cardinal;  
begin  
  Result := True;    // Result = True  
  if not odd(Zahl) OR (Zahl <= 5) then    // Ist die Zahl nich ungerade oder kleiner als 5, dann  
  begin  
    if (Zahl <> 2) AND (Zahl <> 3) AND (Zahl <> 5) then    // Ist die Zahl nicht 2 und nicht 3 und nicht 5, dann  
      Result := False;    // Result = False  
    Exit;                 // Exit  
  end;  
  Teiler := @PrimS[0];    // Teiler = @PrimS[0]  
  Wurzel := Trunc(sqrt(Zahl));    // Wurzel aus der Zahl  
  while Teiler^ <= Wurzel do    // Solange Teiler^ <= Wurzel ist, mache  
  begin      
    if Zahl mod Teiler^ = 0 then    // Ist Zahl / Teiler^ = Rest 0, dann  
    begin  
      Result := False;    // Result = False  
      Break;    // Break  
    end;  
    Inc(Teiler);    // Teiler erhöhen um 1  
  end;  
end;

Delphi-Quellcode:

procedure TMainForm.StartButClick(Sender: TObject);  
var  
  Start, Ende: Real;  
  Z: PCardinal;  
  X, LPrim: Cardinal;  
  PrimF: TStringList;  
begin  
  try  
    Von := StrToInt(VonEdit.Text);    // Start  
    Bis := StrToInt(BisEdit.Text);    // Endwert  

 
    if Bis > 10 then  
      SetLength(PrimS, Trunc(0.4*Bis-(Bis/4)))    // Größe des Array: 0.4*Bis-(Bis/4)  
    else  
      SetLength(PrimS, 4);  

 
    LPrim := 0;    // Letze Prim = 0  
    Z := @PrimS[0];     // Gefundene Prims = 0  

 
    if (Von >= 0) AND (Bis >= 0) AND (Von < Bis) then    // Von >= 0; Bis >= 0; Von < Bis;  
    begin  
      Start := GetTickCount;    // Start-Zeit  

 
      for X := Von to Bis do    // Schleife: Startwert -> Endwert  
      begin  
        if Prim(X) then    // Funktion ausführen, wenn Prim dann  
        begin  
          Z^ := X;    // Prim in Array schreiben  
          Inc(Z);    // Z erhöhen um 1  
          LPrim := X;    // Letze Prim = X  
        end;  
        if X mod 20000 = 0 then    // Wenn X : 20.000 = Rest 0, dann  
        begin  
          Application.ProcessMessages;    // Anwendung aktualisieren  
          PrimLab.Caption := 'Aktuelle Primzahl: ' + IntToStr(LPrim);    // Akt. Primzahl anzeigen  
        end;  
      end;  

 
      Ende := GetTickCount;    // End-Zeit  
      DauerLab.Caption := 'Diese Überprüfung hat ' + FloatToStr((Ende - Start) / 1000) + ' Sekunden gedauert.';    // Dauer anzeigen  

 
      PrimLab.Caption := 'Speichern...';    // "Speichern..." anzeigen  

 
      Z := @PrimS[0];    // Z auf 0 stellen  
      PrimF := TStringList.Create;    // Stringlist erzeugen  

 
      for X := 0 to Length(PrimS)-1 do    // Von 0 bis Größe des Array  
      begin  
        if Z^ = 0 then    // Wenn Z^ = 0, dann  
          Break;    // Break  
        PrimF.Add(IntToStr(Z^));    // Prim in Stringlist schreiben  
        Inc(Z);    // Z erhöhen um 1  
      end;  

 
      PrimF.SaveToFile('Prim.txt');    // Stringlist speichern  
      PrimF.Free;    // Stringlist freigeben  

 
      PrimLab.Caption := 'Aktuelle Primzahl: ' + IntToStr(LPrim);    // Akt. Primzahl anzeigen  
    end  
    else  
      ShowMessage('Ungültige Eingabe(n)!');    // Bei falschen Eingaben, Nachricht anzeigen  
  except  
    ShowMessage('Es ist ein Fehler aufgetreten!');    // Wenn Fehler auftritt, Nachricht anzeigen  
  end;  
end;

Das Programm überprüft 10.000.000 Zahlen in erstaunlichen 6 Sekunden.
Und das Speichern geht so schnell, dass man "Speichern..." gar nicht sieht.

[Horst_]

Hallo,

Es geht doch noch schneller (erst seit 2003? )
EcPrime1.4 ist aber in C++ geschrieben.
Das siebt alle Primzahlen von 1 bis 1e9 in 1.4 Sekunden statt 2.6 (alzaimar's delphi Version von primgen97) (Pentium M 1.7 Ghz, WinXp) meine Tp-Verion mit Delphi7 kompiliert 7.6 s (2.5s nur für's zählen da sind die anderen fertig )
Ich kann mir nicht vorstellen, dass der Übergang von C++ nach Delphi die Zeiten halbieren sollte.
Gruß Horst

[KarYn-To]

Ich versteh den Code nicht öÖ??? Aber ich hab eine Frage, weil ich sowas mal probiert habe.

Delphi-Quellcode:

function GetPrimes: Integer;
var Max, X, Y, Z, Temp, Prim: Integer;
begin
  With Form1 Do
  Begin
    X := 2;
    Z := 0;
    Max := 20000;
    For Y := 2 To Max Do
     lPrime.Items.Add(IntToStr(Y));
     While Z <> lPrime.Items.Count - 1 Do
     Begin
       Prim := StrToInt(lPrime.Items.Strings[Z]);
       While (X*Prim) < (Max + Prim) Do
       Begin
         Temp := X * Prim;
         lPrime.Items.Delete(lPrime.Items.IndexOf(IntToStr(Temp)));
         X := X + 1;
       End;
       Z := Z + 1;
       X := 2;
       Application.ProcessMessages;
     End;
  End;
end;

(* Der Code macht nichts anderes als alle Zahlen von 2 bis Max in die ListBox
   lPrime einzutragen und dann mit der zwei zu Beginnen und alle anderen
   Werte rauszustreichen *)

(* Der obige Code ist nur Schwachsinn und eh Fehlerhaft... *hust* *)

Führt das hier nicht im Endeffekt auch zum Erfolg ? Und was sind Sprungtabellen, etc. etc. etc. ?
Hoffe auf Antwort !

EDIT: <~ Bitte schlagt die Unwissenden nicht =) Sorrrrrrrry... das hier ist hohe Entwicklungskunst.