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]