Antiek priemgetallenalgoritme krijgt upgrade

Met de ‘zeef van Eratosthenos’ kun je elk priemgetal vinden dat kleiner is dan een opgegeven getal. De tweeduizend jaar oude methode krijgt nu een update.

Priemgetallen zijn alleen deelbaar door 1 en door zichzelf. In de rekenkunde nemen ze een erg bijzondere plaats in, want elk natuurlijk getal kun je vormen door priemgetallen met elkaar te vermenigvuldigen.

Dat wisten de oude Grieken al, of tenminste de Griekse wijsgeren die zich inlieten met de edele kunst van de wiskunde. De Ptolemaeïsche natuurfilosoof Eratosthenes bedacht in 240 voor Christus een methode om priemgetallen op te sporen. Zijn zogeheten ‘zeef’ werkt als volgt. Neem bijvoorbeeld de getallen 1 tot en met 100. Eerst ‘zeef’ je alle veelvouden van 2 weg, het eerste priemgetal. Je haalt dus 2, 4, 6, 8 enzovoort weg. Daarna begin je opnieuw bij het kleinste overgebleven getal: dan haal je alle veelvouden van 3 weg. Vervolgens moet je eerst de veelvouden van 5 en daarna die van 7 wegzeven, en zo ga je verder tot je niet meer verder kunt. Elk getal waarbij je het proces begint – en dat dus niet al is weggehaald – is een priemgetal.

De methode werkt prima om relatief kleine priemgetallen op te sporen. Maar voor heel grote getallen ze is onbruikbaar, door de enorme tijd en geheugen die computers ervoor nodig hebben. Daarom verbeterden wiskundigen in de jaren zestig van vorige eeuw de zeef. Ze bekwamen dat een computer voor alle priemgetallen kleiner dan een opgegeven getal N, nog maar een aantal geheugenunits nodig had gelijk aan de vierkantswortel van dat getal N.

Toch bleek die vernieuwde methode ook onpraktisch, voor zeer grote waarden van N. Daarom verzon een Duitse wiskunde wederom een upgrade. Hij maakt daarvoor gebruik van de rationele benadering van reële getallen – kommagetallen opschrijven als een breuk, zoals 355/113 voor het getal pi.

In de upgrade is het benodigde aantal geheugeneenheden om alle priemgetallen kleiner dan N te vinden, nog slechts gelijk aan de derdemachtswortel van N, maal een wortel van haar haar logaritme. Met deze 21ste eeuwse versie van de zeef van Eratosthenes kunnen een miljard getallen ‘doorzeefd’ worden met slechts 7.500 geheugenunits.


Gerelateerde artikels

400 jaar sinds de eerste mechanische rekenmachine

400 jaar sinds de eerste mechanische rekenmachine

We zijn in het begin van de zeventiende eeuw, een tijd van grote astronomen, zoals Tycho Brahe, en Johannes Kepler. Het beroep van astronoom was toen moeilijker uit te oefenen dan nu. Natuurlijk geen computers, maar dat was niet het enige probleem. Er was toen ook nog geen deftige voorstelling van getallen voorhanden, de berekeningen gebeurden allemaal met breuken, en ja, met de hand dus. Ook de logaritme, het hulpmiddel bij uitstek bij zware berekeningen, was nog niet uitgevonden. Dat gebeurde pas in 1617 door John Napier. En ongeveer toen, ook dankzij onze Simon Stevin, geraakte alles in een stroomversnelling. In 1623 al was er de eerste mechanische rekenmachine, speciaal ontworpen voor Kepler door Wilhelm Schickard, een collega-astronoom. Het was het eerste rekentoestel met geautomatiseerde `overdrachten'.