Delphi errechnet keine Primzahlen größer als 5000

[Jonas Shinaniganz]

Weil du schon so mutig warst und deinen ganzen Code geteilt hast, habe ich mal die gröbsten Sachen rausgenommen
Dinge wie "Globale Variablen", "redundante Abfragen" und "doppelte Initialisierung von Variablen" müssen ja nicht sein. Auch wenns mal schnell sein muss...
Vielleicht bringts dir was:

Delphi-Quellcode:

unit Unit1;

interface

uses
  Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
  Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls;

type
  TForm1 = class(TForm)
    Edit1 : TEdit;
    Button1 : TButton;
    procedure Button1Click(Sender: TObject);
  public
    Max : integer;
    Primzahlen : array of Integer;
    Primzahl : Boolean;
    procedure OutPutMessage;
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
var
  I, F : Integer;
begin
  max := strtoint(edit1.Text);
  I := 1;

  repeat

    if (I > 0) then
    begin
      Primzahl := true;

      for F := 2 to I - 1 do
      begin
        if ((I mod F) = 0) then
        begin
          Primzahl := false;
          Break;
        end;
      end;

      if (Primzahl) then
      begin
        SetLength(Primzahlen, High(Primzahlen) + 2);
        Primzahlen[High(Primzahlen)] := I;
      end;
    end;

    I := I + 2;
  until(I >= Max);

  OutPutMessage;
end;

procedure TForm1.OutPutMessage;
var
  XC : String;
  I : Integer;
begin
  for I := 0 to High(Primzahlen) do
  begin
    XC := XC + inttostr(Primzahlen[I]) + ', ';
  end;
  showmessage(XC);
end;

end.

Da kann man selbstverständlich immernoch einiges optimieren und besser machen. Grüße

[Furtbichler]

Und dann ist das noch so, das alle Primzahlen > 3 der Form 6n+/-1 sind. Also kann man alle Primzahlen so prüfen

Delphi-Quellcode:

// 2,3 => Primzahl
p := 5;
repeat
  If IsPrime(P) then AddToPrimeList(P);
  If IsPrime(P+2) then AddToPrimeList(P+2);
  inc(P,6);
until p>maxint-6; // oder so ähnlich

Und die Funktion IsPrime prüft nicht bis Wert/2, sondern nur bis Sqrt(Wert) und da auch nur mit allen bisherigen Primzahlen, also:

Delphi-Quellcode:

Function IsPrime (P : Integer): Boolean;
Begin
  MaxP := Trunc(Sqrt(P));
  I := 0;
  While (Primes[I]<MaxP) do 
    If P Mod Primes[I]<>0 then 
      exit(false) 
   else 
      inc(I);
  exit(true)
End;

Ist aber ungetestet.

Und noch eigentlicher verwendet man 'Sieve of Atkin' oder 'Sieve of Eratosthenes'. Da bekommt man dann alle Primzahlen < 2^31 in so 1-2 Sekunden, wenn ich mich richtig erinnere.