Primzahl

[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!