Primzahlen im Intervall (2; n) ermitteln

[shmia]

Hier meine Verbesserungen:
* Ich verwende TBits statt array of Boolean. Benötigt ca. 8 mal weniger Speicher. Ausserdem Schutz vor Speicherüberschreibung

* Das eigentliche Sieb arbeitet schneller, da auf die Modulo Operation verzichtet wird.
(Schade, da Delphi die For-Schleife mit Schrittweite > 1 nicht kann.
Dann muss es halt eine While-Schleife sein)

Delphi-Quellcode:

unit SieveOfEratosthenes;

interface 

uses 
  Classes;

type
  TSieveOfEratosthenes = class(TPersistent) 
    private 
      fMaxValue: Cardinal; 
      fSieve: TBits; 
      fPrimes: array of Cardinal;
      fPrimesFound : Cardinal;
      function GetPrimes(const i: Cardinal): Cardinal;
      function GetPrimesFound: Cardinal;
      procedure SetMaxValue(AValue: Cardinal);
    public
      constructor Create(AMaxValue: Cardinal);
      destructor Destroy;override;
      property MaxValue: Cardinal read fMaxValue write SetMaxValue;
      property Primes[const index: Cardinal]: Cardinal read GetPrimes;
      property PrimesFound: Cardinal read GetPrimesFound;
      procedure FindPrimes(); 
  end; 

implementation 

{ TSieveOfEratosthenes } 

constructor TSieveOfEratosthenes.Create(AMaxValue: Cardinal); 
begin 
   inherited Create;
   fSieve := TBits.Create;
   MaxValue := AMaxValue;
end; 

destructor TSieveOfEratosthenes.Destroy;
begin
   fSieve.Free;
  inherited;
end;

procedure TSieveOfEratosthenes.FindPrimes;
var i, j: Cardinal;
begin
  fSieve.Size := 0;  // alten Inhalt wegwerfen
  fSieve.Size := MaxValue+1;  // speicher für Sieb reservieren

  // hier wird gesiebt
  i := 2;
  while i*i <= MaxValue do begin
    if fSieve.Bits[i] = false then
    begin
      j := i*i;
      while j <= MaxValue do
      begin
        fSieve.Bits[j] := true;
        Inc(j, i);
      end;
    end;
    i := i + 1;
  end;

  // Zählen der gefundenen Primzahlen
  fPrimesFound := 0;
  for i := 2 to MaxValue do
    if fSieve.Bits[i] = false then
      Inc(fPrimesFound);

   // speichern der Primzahl
   SetLength(fPrimes, fPrimesFound);
   j := 0;

  for i := 2 to MaxValue do begin
    if fSieve.Bits[i] = false then
    begin
      fPrimes[j] := i;
      Inc(j);
    end;
  end;
end;

function TSieveOfEratosthenes.GetPrimes(const i: Cardinal): Cardinal; 
begin 
  Result := fPrimes[i]; 
end; 

function TSieveOfEratosthenes.GetPrimesFound: Cardinal; 
begin 
  Result := Length(fPrimes); 
end; 

procedure TSieveOfEratosthenes.SetMaxValue(AValue: Cardinal); 
begin
  fMaxValue := AValue;
end; 

end.