Re: Eenvoudige priemtest

Dit is een reactie op vraag 62982

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 Lm
Iets anders - donderdag 26 augustus 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.

donderdag 26 augustus 2010

©2001-2024 WisFaq