Primzahl

[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

Mfg Coffeecoder

[sHoXx]

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

[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
  while i <= 2*SieveSize do ausgestestet und es hat funktioniert. Mathematisch kann ich es leider nich begründen!

Have fun!

[scrat1979]

Kann die Zeile
  if zahl mod teiler=0 then prim := false; nicht noch optimiert werden in

prim := not (zahl mod teiler = 0); ??? Hab den Thread aber nur überflogen...

Grüsse,
SCRaT