WisFaq!

Re: Eenvoudige priemtest

Dag Hennie,
Tussen 2 en 87 liggen volgende priemgetallen(volgens mijn zeef of heb ik nog iets over het hoofd gezien,):
2,3,5,7,11,13,17,19,23,31,41,43,53,59,61,67,71,79,83.
Ik heb nog geen "lamme arm" maar deze methode van Erastosthenes kan je toch niet behouden voor een test van n= 103.799 bijvoorbeeld. Wat doen bij zeer grote getallen dan ??
Groeten,
Rik

Rik Lmemens
26-8-2010

Antwoord

Hallo, Rik.

Een eenvoudige en snelle weg is er voor zeer grote getallen n niet.

Overigens gaat het voor een middelgrote n zoals uw n=103799 met een pascal computerprogramma nog snel genoeg (als geheledeel(wortel(n)) hoogstens maxint=32767 is, lukt het op deze manier):

program priemtestmetzeef;
var k,q:integer; m,n:real; priem:boolean;
begin
while true do
begin
writeln; writeln('n=?'); readln(n);
priem:=true; q:=trunc(sqrt(n));
for k:=2 to q do
begin
m:=k;
while mn do m:=m+k;
if m=n then begin priem:=false; writeln(k:5,' is deler') end
end;
if priem then writeln('priem') else writeln('niet priem')
end
end.

Probeer het maar: je vindt dat 103799 geen priemgetal is, want deelbaar door 23.

NB: Als je een lijst met priemgetallen kleiner dan of gelijk aan wortel(n) paraat hebt, kun je natuurlijk ook volstaan met de staartdelingen door deze priemgetallen te proberen.

hr
26-8-2010