Hauptmenü
Home
Delphi
C# / .NET
Freepascal
Firebird
OPF
Tutorials
Tipps und Tricks
Links
Suche
Impressum
Primzahlen ermitteln PDF E-Mail
Geschrieben von Lemmy   
Sonntag, 19. Februar 2006
Worum es geht:
Hier stelle ich eine komplizierte Methode vor (die aber optimaler arbeitet) und eine ganz einfache Methode, die jedoch nicht so optimal ist.
Was sind Primzahlen? Das sind ganze positive Zahlen von 2 bis unendlich, die nur durch 1 oder sich selber teilbar sind.  
Wie ermittelt man Primzahlen? Es gibt mehrere mehr oder weniger komplizierte Verfahren. Ich möchte ein einfaches vorstellen, was allerdings nicht für beliebig große Zahlen (ab ca. 100000) geeignet ist. Dafür gibt es sicherlich noch bessere Algorithmen. Für das Verfahren, das ich vorstellen möchte, gilt kurz gesagt folgende Regel: Man kann Primzahlen aus bisher bekannten Primzahlen ermitteln. Man kann aus diesen bekannten Primzahlen soviel neue ermitteln, dass man danach insgesamt die Primzahlen bis zum Wert des Quadrates des höchsten Wertes der alten Primzahlen erhält, z.B. man hat die Primzahlen von 2 bis 7 - daraus kann man die weiteren Primzahlen bis 49 (also 7²) ermitteln Daraus kann man wiederum die Primzahlen bis 2401 (49²) bestimmen, bis man alle gefunden hat, die man sucht.
Umsetzung als Programm (in Worten)
  1. Schaffe dir einen kleinen Anfangsvorrat an Primzahlen
  2. Schaffe dir eine Zahlenliste von A bis B     --> A ist die größte dir bekannte Primzahl aus obiger Liste plus 1     --> B ist das Quadrat der größten bisher bekannten Primzahl
  3. Streiche aus dieser Liste alle Zahlen raus, die durch die die bisherigen Primzahlen teilbar sind
  4. Die Liste enthält nun nur noch Primzahlen - diese können zu den anderen hinzugefügt werden
  5. Nun wird Punkt 2 wieder ausgeführt, bis man bei der Grenze, bis wohin man Primzahlen sucht, angelangt ist - dann nimmt man logischerweise statt dem Quadrat der bisherigen größten Primzahl den gesuchten Grenzwert.
Umsetzung als Programm (Quelltext)
Erstelle eine neue Anwendung mit folgenden Komponenten: ListBox1, Edit1, Button1
Das OnClick-Ereignis des Buttons muss folgendermaßen aussehen:

procedure TForm1.Button1Click(Sender: TObject);
var PrimZahlen :Array of Integer;
PruefReihe :TStringList;
j,Max_AltePrimZahlen :Integer;
i,MaxSuche  :LongInt;
Ende :Boolean;
begin
//die ersten 15 Primzahlen werden vorgegeben:
  SetLength(PrimZahlen,15);
  PrimZahlen[0]:=2; PrimZahlen[1]:=3; PrimZahlen[2]:=5; PrimZahlen[3]:=7;
  PrimZahlen[4]:=11; PrimZahlen[5]:=13; PrimZahlen[6]:=17; PrimZahlen[7]:=19;
  PrimZahlen[8]:=23; PrimZahlen[9]:=29; PrimZahlen[10]:=31; PrimZahlen[11]:=37;
  PrimZahlen[12]:=41; PrimZahlen[13]:=43; PrimZahlen[14]:=47;
//mit dem bekannten Satz Primzahlen werden weitere bestimmt
//daraus resultiert ein groesserer Satz Primzahlen, mit dem wiederum weitere
//bestimmt werden, so lange, bis die vom Benutzer eingegebene Obergrenze
//erreicht ist
PruefReihe:=TStringList.Create;
  PruefReihe.Clear;
  Ende:=False;
  Repeat
    MaxSuche:=PrimZahlen[High(PrimZahlen)];
    If StrToInt(Edit1.Text)>MaxSuche*MaxSuche Then MaxSuche:=MaxSuche*MaxSuche
    Else Begin
      MaxSuche:=StrToInt(Edit1.Text);
      Ende:=True; //damit das Repeat nach Berechnung
//dieser Zahlen verlassen wird
    End;
    PruefReihe.Clear;
//Stringlist mit den Zahlen von hoechste bekannte Primzahl+1 bis eben
//ermittelte Zahl fuellen:
For i:=PrimZahlen[High(PrimZahlen)]+1 to MaxSuche Do
        PruefReihe.Add(IntToStr(i));
    For j:=0 to High(PrimZahlen) do Begin
      For i:=0 to PruefReihe.Count-1 Do Begin
//Verlassen kann erst hier bestimmt werden, denn erst hier ist bekannt,
//ob durch das Herauskuerzen von Zahlen nicht schon das Ende der StringList
//erreicht wurde:
        If i>PruefReihe.Count-1 Then Break;
//Ist die Zahl durch die momentane Primzahl teilbar, wird sie gestrichen:
        If (StrToInt(PruefReihe.Strings[i]) mod PrimZahlen[j]=0) AND
           (StrToInt(PruefReihe.Strings[i])<>PrimZahlen[j])
           Then PruefReihe.Delete(i);
      End;
    End;
    Max_AltePrimZahlen:=High(Primzahlen);
//StringList enthaelt nur noch die neuen Primzahlen-->ins Array uebertragen:
SetLength(PrimZahlen,High(PrimZahlen)+1+PruefReihe.Count);
//fuegt dem Primzahlen-Array die neuen Primzahlen hinzu:
    For i:=0 to PruefReihe.Count-1 do begin
      PrimZahlen[Max_AltePrimZahlen+i+1]:=StrToInt(PruefReihe.Strings[i]);
    end;
  Until Ende;

  PruefReihe.Free;
//Primzahlen ausgeben:
 ListBox1.Clear;
  For i:=0 To High(PrimZahlen) Do ListBox1.Items.Add(IntToStr(PrimZahlen[i]));
  Form1.Caption:=IntToStr(ListBox1.Items.Count)+' PrimZahlen gefunden';
  SetLength(PrimZahlen,0);
//Der Code ist sicherlich noch optimierbar
end;

Hier die einfache Lösung:  
Man braucht noch zwei Edit-Felder, eine Listbox und ein Label. In die beiden Edit-Felder trägt man die Grenzen des Bereichs ein, in dem Primzahlen gesucht werden sollen.

function tform1.prim(zahl:integer):boolean;
var i:integer;
begin
  result:=true;
  for i := 2 to round(sqrt(zahl)) do
    if zahl mod i=0 then
result:=false;
end;

procedure TForm1.Button1Click(Sender: TObject);
var i:integer;
begin  
ListBox1.Clear;
  for i:=StrToInt(Edit1.Text) to StrToInt(Edit2.Text) do  
if prim(i)=true then
ListBox1.Items.Add(IntToStr(i));
Form1.Caption:=IntToStr(ListBox1.Items.Count);
end;
 
< Zurück   Weiter >
[ Zurück ]

Design by JoomlaDesigns