Hello
Ik ben voor mijn examen Toegepaste Discrete algebra op zoek naar een efficiente en eenvoudige priemtest, maar mijn eerste zoekresultaten leveren niet meteen iets op.
De meeste priemtesten gebruiken machtsverheffingen blijkbaar. Dit is niet echt een optie, gezien het examen zonder rekentoestel is. Bepaalde machtsverheffingen zijn natuurlijk wel te vereenvoudigen met de kleine stelling van Fermat, maar dat is toch ook niet altijd een optie.
Weten jullie raad?Michiel
25-8-2010
Het meest voor de hand liggend is de factorisatietest:
n is priem dan en slechts dan als n niet deelbaar is door een van de getallen 2,3,..,geheledeel(Ön) (want als n niet priem is, is n het product van twee getallen waarvan er een hoogstens Ön is).
Als n door een bepaald getal k niet deelbaar was, zal n ook niet deelbaar zijn door veelvouden van k.
Dit leidt tot de zeef van Eratosthenes:
1) Schrijf op een groot vel papier de getallen 2 3 4 5 6 7 8 9 10 11 12 etc (tot en met n).
2) Zet een cirkel om 2, en streep de veelvouden van 2 door. (Dus streep 4,6,8,10, etc door.)
(De doorgestreepte getallen zijn niet priem, dus zodra je n hebt doorgestreept, kun je de hele procedure stopzetten; dit geldt ook voor het vervolg.)
3) Omcirkel het eerste nog niet doorgestreepte of omcirkelde getal in de lijst, en streep de veelvouden hiervan door. (De eerste keer dat je dit doet, omcirkel je 3 en streep je 6,9,12,15, etc door; sommige getallen waren al doorgestreept, maar dat geeft niet.)
4) Herhaal stap 3) totdat alle getallen tot en met geheledeel(Ön) ofwel omcirkeld zijn, ofwel doorgestreept. De omcirkelde getallen zijn priem.
5) Als n nu nog niet doorgestreept is, is n priem.
6) Als je nog tijd over hebt, kun je cirkeltjes zetten om alle niet doorgestreepte getallen in de lijst: die zijn ook allemaal priem.
Voer dit om te oefenen eens uit met n=87.
Als je geen lamme arm wilt krijgen, kun je de factorisatietest zonder zeef uitvoeren. Je moet dan wel steeds goed onthouden waar je gebleven bent.
Natuurlijk kun je daar wel weer een papier bij gebruiken.
Andere priemtesten kan men niet meer eenvoudig noemen.
Zie desgewenst http://nl.wikipedia.org/wiki/Priemgetaltest .
hr
26-8-2010
#62982 - Getallen - Student universiteit België