aus Paswiki Turbo Pascal, der freien Wissensdatenbank

Beschreibung

Hier werden die Primzahlen mit Hilfe des Siebs des Eratothenes aufgelistet. - Eines der schnellsten bekannten Verfahren, um große Bereiche zu durchsuchen.

Programm

Sucht die Primzahlen in extrem schnellem Tempo !!!

Da die Zeichenausgabe das Tempo exponential ansteigen lassen würde, sei diese unberücksichtig, kann aber auf Wunsch auch eingebaut werden - einfach ins Gästebuch schreiben!

Bei einem 1.5 Ghz-Prozessor ergaben sich folgende Durchschnittswerte:

Obergrenze	Zeit in Sek.
500.000 (0.5 Mio)	0.04
1.000.000 (1 Mio)	0.10
5.000.000 (5 Mio)	0.38
10.000.000 (10 Mio)	0.75
25.000.000 (25 Mio)	1.97
50.000.000 (50 Mio)	4.03
100.000.000 (100 Mio)	8.32

---

{$N+}
uses dos;
type teil=array[0..60000] of boolean;

var
data            : array[1..60000] of boolean;
teiler          : ^teil;
i,j,count,sum   : longint;
a,x,k,runde     : integer;
endw,ende,bis   : longint;
h,m,s,s100      : word;
time1,time2     : real;
endwert,ew      : longint;
min,ew2,zaehlen : longint;


begin

writeln('Sieb des Erastosthenes');
writeln('======================');
writeln;
   writeln('Bis zu welcher Obergrenze  ?');
    readln(ende);   bis:=ende;
   writeln('---------------');

  ende :=( ende div 60000 ) +1;

   gettime(h,m,s,s100);
   time1:=3600*h + 60*m + s + (s100/100);

   new(teiler);

 for i:=1 to 60000 do
 if odd(i) then
 data[i]:=false;

     endwert:=60000; zaehlen:=60000;
 if endwert>bis then begin endwert:=bis; zaehlen:= bis mod 60000; end;

      for j:=2 to trunc(sqrt(endwert)) do
      begin

      if odd(j) then
      begin

      sum:=j;
      for i:=2 to (60000 div j) do
      begin

      sum:=sum+j;
      if odd(i)  then begin

      if (sum>0) and (sum<=60000) then teiler^[sum]:=true;

      end;
      end;
      end;
      end;

      for i:=1 to zaehlen do
      if odd(i) then
      if teiler^[i]=false then inc(count);

{----------------------------}

for runde:=2 to ende do begin

     ew:=endwert;

     endwert:=endwert + 60000; min:=min+zaehlen;
     if endwert>bis then begin endwert:=bis; runde:=ende;  zaehlen:= bis mod 60000; end;

     {wenn die Primzahlengrenze höher als der endwert sind, wird nur bis zur differenz ausgezählt}

      for j:=2 to trunc(sqrt(endwert)) do
      begin

      if teiler^[j]<>true then begin
      if odd(j) then
      begin


      for i:=(ew div j) to (endwert div j) do
      begin

      if odd(i) then begin

      sum:=(j*i)-min;

      if (sum>0) and (sum<=60000) then data[sum]:=true;

      end;
      end;
      end;
      end;
      end;


      for i:=1 to zaehlen do
      begin
      if odd(i) then begin
        if (data[i]=false) then inc(count)
        else data[i]:=false;
          end;
          end;
end;
{----------------------------}

    dispose(teiler);

     gettime(h,m,s,s100);
     time2:=3600*h + 60*m + s + (s100/100);

       writeln(count,' Primzahlen');
      writeln('Es hat ',time2-time1:0:2,' Sek. gedauert.');

      readln;
   end.

---

--Gastarbeiter 14:34, 17. Mär 2006 (CET)

---