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 21ˢᵗᵉ eeuwse versie van de zeef van Eratosthenes kunnen een miljard getallen ‘doorzeefd’ worden met slechts 7.500 geheugenunits.
Noten
Harald Helfgott, University of Göttingen, Duitsland in Mathematics of Computation
Schrijf je in op onze nieuwsbrief
En blijf op de hoogte van de laatste inzichten in wetenschap en technologie.