aus Paswiki Turbo Pascal, der freien Wissensdatenbank

Beschreibung

Hier wird der Fermatsche Primzahltest realisiert. Er besagt, dass nur bei Primzahlen (und starken Pseudoprimzahlen, die allerdings sehr selten sind) der Algorithmus a^(n-1) mod n ( wobei 1 < a < n-1 ) 1 als Ergenis hat.

Da aber beispielsweise schon 2^17000 mod 17001 in Turbo Pascal nicht auf normalen Wege möglich ist, muss dieser Primzahltest mit Arrays in die man die Zahlen aufteilt und packt, durchgeführt werden.

Somit wird das Ganze ein wenig zeitaufwendiger, es ist aber möglich mit Werten bis zu 10^65000 zu operieren, d.h. das hier veröffentliche Programm kann Zahlen bis zu ca. 200.000 auf prim prüfen.

Programm

uses dos;
type mein=0..159;

var  null:boolean;
     m2,nenner2,hoch,hochmod,i,x,j,n,c,teiler,hoch2,wieoft:longint;
     ab,nenner,g:string;
     h,h2,m,mda,s,s2,s100,s1002:word;
     time1,time2:real;
     zahl:array[0..60000] of mein;
     code,plus:integer;

procedure teilen;
begin
val(ab,m2,code);
for c:=x+1 downto 1 do
begin
str(zahl[c],g);
nenner:=nenner+g;
val(nenner,nenner2,code);
if nenner2>=m2 then
begin
nenner2:= nenner2 mod m2;
str(nenner2,nenner);
end;
end;
end;

procedure mal;
begin
plus:=0;
for i:=1 to hochmod do begin
zahl[i]:=zahl[i]*teiler + plus;
plus:=0;
if zahl[i]>9 then begin plus:=zahl[i] div 10; zahl[i]:=zahl[i]-(10*plus);end;
end;
end;


begin
writeln('Zahl = ?');
readln(hoch);
hoch:=hoch-1; hoch2:=hoch;  teiler:=2;

repeat
if frac(hoch2/teiler)=0 then begin hoch2:=hoch2 div teiler; teiler:=teiler*teiler end;
until frac(hoch2/teiler)<>0;
if teiler>16 then teiler:=16;

wieoft:=1;
if teiler>2 then wieoft:=round(sqrt(teiler));

writeln('Zahl = ',hoch+1);
str(hoch+1,ab);
if hoch >100 then hochmod:=(hoch div 3) else hochmod:=hoch;

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

if (odd(hoch)) and (hoch>2) then begin writeln('keine Primzahl !');readln;halt;end
else begin
zahl[1]:=1;


for j:=1 to hoch div wieoft do
mal;

write('2 ^ ',hoch,' = ');

for j:=hochmod downto 1 do
begin
if zahl[j]<>0 then begin null:=true;end;
if null=true then write(zahl[j]);
end;

for j:=hochmod downto 1 do
begin
if zahl[j]<>0 then begin x:=j;break;end;
end;

gettime(h2,mda,s2,s1002);  time2:=mda*60+s2+1/s1002;

writeln;
writeln;
writeln(time2-time1:0:2,' sek.');
writeln(' = ',x,'-Stellen lange Zahl');
writeln('---------');
teilen;
write('Rest ');
writeln(nenner,' ! ');
writeln;
if nenner='1' then writeln('=> Primzahl');

readln;
end;
end.

---

Gastarbeiter 17:18, 18. Apr 2006 (CEST)

---