AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Code-Bibliothek Library: Algorithmen Delphi Primzahlen im Intervall (2; n) ermitteln

Primzahlen im Intervall (2; n) ermitteln

Ein Thema von Meflin · begonnen am 23. Aug 2006 · letzter Beitrag vom 14. Sep 2006
Antwort Antwort
Benutzerbild von Meflin
Meflin

Registriert seit: 21. Aug 2003
4.856 Beiträge
 
#1

Primzahlen im Intervall (2; n) ermitteln

  Alt 23. Aug 2006, 12:37
Aloha!

Mit Hilfe des sg. Bei Google suchenSieb 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]
Angehängte Dateien
Dateityp: txt 1000000_203.txt (602,5 KB, 31x aufgerufen)
  Mit Zitat antworten Zitat
shmia

Registriert seit: 2. Mär 2004
5.508 Beiträge
 
Delphi 5 Professional
 
#2

Re: Die Primzahlen im Bereich von 2..n ermitteln

  Alt 14. Sep 2006, 15:42
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.
Andreas
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 06:41 Uhr.
Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2019 by Daniel R. Wolf