Primzahl

[Jumpy]

Weitere Optimierung wäre:

teiler:=3;

in zusammenarbeit mit

zahl:=zahl+2;

und

teiler:=teiler+2;

So werden alle geraden Zahlen (>2) übersprungen, da sie ja eh nicht prim sind.

[Wolfgang Mix]

zusammengefasst:

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var n, teiler, zahl :integer;
    wurzel :real;
    prim :boolean;
begin
  ListBox1.clear;
  n:=strtoint(Edit1.text);
  ListBox1.items.Add('2');
  zahl:=3;

  while zahl<=n do
  begin
    prim:=true;
    teiler:=3;
    wurzel:=sqrt(zahl);
    while (teiler <= wurzel) and (prim) do
    begin
      if zahl mod teiler=0 then prim := false;
      inc(teiler,2) ;
    end;

  if prim then
    listbox1.Items.Add (inttostr(zahl));
  inc(zahl,2);

  end;
end;

[implementation]

Eine andere Lösungsidee:

Man nehme ein Array of Boolean und befüllt es mit true.
Jetzt fängt man mit der 2 an (x := 2).
Und geht zunächst jedes zweite Feld durch und setzt es auf false.
Dann stehen arr[4], arr[6] usw. alle auf false.

Nun macht man mit der 3 weiter und schaut sich arr[3] an.
arr[3] ist true, also ist 3 eine Primzahl.
Nun geht man von hier aus wieder jedes dritte Feld durch und setzt es auf false.
Dann stehen arr[9], arr[15] und arr[21] ebenfalls auf false.

Nun die 4: arr[4] ist false -> keine Primzahl!

Weiter zur 5: arr[5] ist true -> Primzahl.
Wieder jedes fünfte Feld auf false setzen: Das wars dann wohl für arr[25] und arr[35].

Weiter zur 6: arr[6] ist false -> keine Primzahl!

Und immer so weiter.

[Coffeecoder]

Interessanter Lösungsansatz!
Man nennt dieses Verfahren das Sieb des Eratosthenes

Mfg Coffeecoder

[implementation]

Zitat:

Zitat von Coffeecoder (Beitrag 1101517)

Interessanter Lösungsansatz!
Man nennt dieses Verfahren das Sieb des Eratosthenes

Mfg Coffeecoder

Danke, ich wusste noch nicht, wie es heißt.

[sHoXx]

ich hab auch mal ein, halb fertiges aber eigentlich funktionsfähiges Primzahl-Programm gemacht,welches nach dem Sieb arbeitet. nicht schön aber selten, geb es euch mal als anhang mit

[Coffeecoder]

Sieht sehr gut aus!
Ich will aber kurz was "meckern" siehe Anhang. Absolute Pfade enden meistens böse :), denn sie sind nicht überall gleich ;)
Aber sonst find ich es gut :thumb:

Mfg Coffeecoder

[sHoXx]

gut da hab ich net dran gedacht, hatte nur kurz was dran ausprobiert :D

[Aphton]

Ich hab mal hier den Sieb des Erastothenes mit Unter- und Obergrenze implementiert.

Delphi-Quellcode:

type
  Int64Arr = Array of Int64;

function SieveOfErastothenes(lowerLimit, upperLimit: Int64): Int64Arr;
var
  SieveSize: Integer;
  Sieve: Array of Boolean;
  procedure _ValidateArgs();
  var
    x: Int64;
  begin
    if lowerLimit > upperLimit then
    begin
      x := lowerLimit;
      lowerLimit := upperLimit;
      upperlimit := x;
    end;
  end;
  procedure _Init();
  begin
    SieveSize := upperLimit - lowerLimit + 1;
    SetLength(Sieve, SieveSize);
    FillChar(Sieve[0], SieveSize, True);
  end;
  procedure _Sieve();
  var
    i, j, k: Int64;
  begin
    i := 2;
    while i < upperLimit do // eventuell unsichere Optimierung: i <= 2*SieveSize
    begin
      if i and 1 = 1 then
      begin
        if i >= lowerLimit then
          while (i < upperLimit) and (not Sieve[i-LowerLimit]) do inc(i);
        j := i;
        if j >= lowerLimit then inc(j, i);
        while j < lowerLimit do inc(j, i);
        while j <= upperLimit do
        begin
          Sieve[j-lowerLimit] := False;
          inc(j, i);
        end;
      end;
      inc(i);
    end;
  end;
  procedure _Pick();
  var
    i, j, k: Int64;
  begin
    i := 0;
    j := 0;
    SetLength(Result, SieveSize);
    while i < SieveSize do
    begin
      if Sieve[i] and ((lowerLimit+i) and 1 = 1) then
      begin
        Result[j] := lowerLimit+i;
        inc(j);
      end;
      inc(i);
    end;
    SetLength(Result, j);
  end;
begin
  _ValidateArgs();
  _Init();
  _Sieve();
  _Pick();
end;

Ein möglicher Aufruf:

Delphi-Quellcode:

var
  Primes: Int64Arr;
  i: Integer;
begin
  Primes := SieveOfErastothenes(100, 200);
  Memo1.Clear;
  for i := 0 to High(Primes) do
    Memo1.Lines.Add(IntToStr(Primes[i]));
end;

Dieser Aufruf - also der Aufruf mit den Argumenten 100 und 200 liefert die Primzahlen zwischen diesen Grenzen (Grenzen eingeschlossen!)

Edit:
Die äußerste Schleife in der _Sieb() Prozedur muss eigentlich nicht bis zu upperLimit durchlaufen werden. Es ginge auch weniger, nur muss ich grad überlegen, um wie viel weniger! (bis SieveSize?)

Edit2:
Habs nun mit

Delphi-Quellcode:

  while i <= 2*SieveSize do

ausgestestet und es hat funktioniert. Mathematisch kann ich es leider nich begründen!

Have fun!

[scrat1979]

Kann die Zeile

Delphi-Quellcode:

  if zahl mod teiler=0 then prim := false;

nicht noch optimiert werden in

Delphi-Quellcode:

prim := not (zahl mod teiler = 0);

??? Hab den Thread aber nur überflogen...

Grüsse,
SCRaT