Primzahlen im Intervall (2; n) ermitteln

[Meflin]

Aloha!

Mit Hilfe des sg. Sieb des Eratosthenes kann man ziemlich einfach alle Primzahlen im Bereich zwischen 2 und N ermitteln. Ich habe hier mal eine einfache Klasse ohne jegliche Optimierung geschrieben:

Delphi-Quellcode:

unit SieveOfEratosthenes;

interface

uses
  Classes, SysUtils;

type
  TSieveOfEratosthenes = class(TPersistent)
    private
      fMaxValue: Cardinal;
      fSieve: array of boolean;
      fPrimes: array of Cardinal;
      fPrimesFound: Cardinal;
      function GetPrimes(const i: Cardinal): Cardinal;
      function GetPrimesFound: Cardinal;
      procedure SetMaxValue(AValue: Cardinal);
    public
      constructor Create(AMaxValue: Cardinal);
      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
  MaxValue := AMaxValue;
  SetLength(fPrimes, 0);
end;

procedure TSieveOfEratosthenes.FindPrimes;
var i, j: Cardinal;
begin
  i := 2; 
  while i*i <= MaxValue do begin
    if fSieve[i] = false then begin
      for j := i*i to MaxValue do begin
        if j mod i = 0 then fSieve[j] := true; 
      end; 
    end; 
    i := i + 1; 
  end; 

  for i := 2 to Length(fSieve) do begin
    if fSieve[i] = false then begin
      SetLength(fPrimes, Length(fPrimes) + 1);
      fPrimes[Length(fPrimes) - 1] := i;
    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);
var i: Cardinal;
begin
  SetLength(fSieve, AValue);
  for i := 2 to AValue do begin
    fSieve[i] := false; 
  end;
  fMaxValue := AValue;
end;

end.

Die gefundenen Primzahlen liegen dann im Array Primes, die Anzahl kann über PrimesFound ermittelt werden!



[edit=CalganX] Mfg, CalganX[/edit]

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