Als je alle priemgetallen in het interval [2, 100] wilt hebben, kun je de zeef van Eratosthenes gebruiken: schrijf de getallen 2 tot en met 100 achter elkaar op en doe dan het volgende: zet een rondje om de 2 en streep de veelvouden van 2 door. Herhaal vervolgens het volgende: zet een rondje om het eerste niet-doorgestreepte getal en streep diens veelvouden door. Aan het eind heb je om alle priemgetallen in het interval een rondje gezet.

Je kunt de zeef ook programmeren, niet alleen voor 100, maar voor een willekeurig interval $[2, n]$. Dat kan bijvoorbeeld met een Boolean array; in het begin is alles ‘true’ en in plaats van doorstrepen maak je de veelvouden ‘false’. Zo’n programma is vrij snel: je hoeft eigenlijk alleen tot aan $√n$ te itereren, want daarna zijn alle niet-doorgestreepte getallen boven $√n$ priem (weet je waarom?).

Je programma kost wel veel werkruimte: net zo veel eenheden als je getal $n$ groot is. Je kunt de werkruimte reduceren tot $√n$ door eerst tot en met $√n$ te zeven en dan telkens in de deelintervallen $[k√n, (k + 1)√n]$ de veelvouden van de priemgetallen uit $[2, √n]$ weg te poetsen. Het opslaan van de priemgetallen kost wel ruimte, maar geen werkruimte. De Engelstalige Wikipedia legt het allemaal mooi uit: http://tinyurl.com/7vosqzu.

Recentelijk heeft Harald Helfgott laten zien dat het met nog minder kan: met $n^{\frac{1}{3}} (\log n)^{\frac{2}{3}}$ eenheden werkruimte. Er is nog geen preprint beschikbaar, maar als die er komt zullen we – als het mogelijk is – in Pythagoras uitleggen hoe het allemaal werkt. (KPH)