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

De draak van Daenerys, Archimedes en het volume van een bol

De draak van Daenerys, Archimedes en het volume van een bol

De gemiddelde leerling zal zich uit zijn schoollessen Archimedes vooral herinneren als de naakte man die uit zijn bad sprong terwijl hij Eureka riep, en niet zozeer als wiskundige. Twee eeuwen na zijn dood vond Cicero het graf van Archimedes, en beschreef hij een grafsteen met een reliëftekening van een bol in een cilinder.  Dit kan kloppen want van al zijn ontdekkingen was Archimedes het meest trots op zijn formule om het volume van een bol te berekenen. Eigenlijk was hij vooral trots op de methode waarmee hij de volumes van de bol, de kegel en de cilinder wist te vergelijken met elkaar.