WisFaq!

Priemgetallen onderzoeken

klopt het dat er geen manier is om uit te zoeken of een groot getal een priemgetal is, behalve door gewoon het te proberen. x te delen door alle priemgetallen x.

Dus als ik wil weten of 4097 (niet zo groot, maar 1 die ik tot nu toe berekend heb) moet ik proberen het te delen door priemgetallen, net zo lang tot ik bij een getal komt wat kan. (in dit geval 17).

mijn vraag is dus eigenlijk, is er geen formule of iets dergelijks om te onderzoeken of x een priemgetal is?

Eric van Dijk
4-3-2004

Antwoord

Als er een kant en klare formule zou zijn, dan was het probleem waar jij mee worstelt geen probleem meer zijn. In principe moet je inderdaad domweg alle mogelijke delingen gaan uitvoeren, maar uiteraard is er in de loop van eeuwen enorm bespaard op deze primitieve aanpak. Men kent inderdaad een aantal krachtige priemgetaltests (bijvoorbeeld de Lucas-Lehmertest), maar dan nog is het voor heel grote getallen een enorme kluif om het wel/niet priem zijn vast te stellen. We hebben het dan overigens over getallen die uit honderduizenden cijfers bestaan! Voor een kleintje als 4097 is het in een handomdraai gebeurd.
Dit soort onderzoek wordt tegenwoordig verricht door grote aantallen computers te laten samenwerken. Ook jij kunt deelnemen aan dit project; zoek maar eens naar GIMPS.
Wie weet, word je nog eeuwig beroemd als ontdekker van het grootste priemgetal van dat moment.

MBL
4-3-2004