De Zeef van Eratosthenes is een algoritme waarmee je alle priemgetallen kan bepalen tot aan een zekere bovengrens. Het is al meer dan tweeduizend jaar bekend. Het is vernoemd naar Eratosthenes van Cyrene, die er de naam Zeef voor bedacht. De Griek Eratosthenes leefde van 276 tot 194 voor Christus. Hij werd vooral bekend door als eerste een nauwkeurige omtrek van de aarde te berekenen.

Het opmerkelijke aan dit algoritme is dat het zonder gebruik te maken van delingen of modulo-operaties toch alle priemgetallen bepaalt. Het behoort nog steeds tot de meest efficiënte algoritmes voor de bepalen van alle priemgetallen binnen een bepaald gebied.

Om bijvoorbeeld alle priemgetallen te bepalen tot aan 1000, ga je als volgt te werk:

  1. Schrijf alle natuurlijke getallen van 2 tot 1000 op een blad papier.
  2. Schrap alle veelvouden van 2.
  3. Het eerste getal dat nu nog niet geschrapt is, is 3. Schrap daarom alle veelvouden van 3.
  4. Het eerste getal dat nu nog niet geschrapt is, is 5. Schrap nu alle veelvouden van 5.

We hebben nu reeds 3 priemgetallen gevonden (2, 3 en 5). Door deze methode voldoende lang vol te houden, vinden we uiteindelijk alle priemgetallen tussen 2 en 1000.

Opgave

Schrijf een klasse Eratosthenes met een methode zeef die alle priemgetallen bepaalt van 2 tot en met een gegeven bovengrens \(n\) en deze netjes naast elkaar afdrukt, met 10 getallen per lijn.

Het ligt misschien voor de hand om je blad papier voor te stellen als een lijst of een tabel (array) van gehele getallen. Een element schrappen (weghalen) uit een lijst of tabel is echter een dure operatie, zeker wanneer ze honderdduizenden elementen bevat. Je moet dus een andere techniek gebruiken.

Bespreek dit eerst met je collega’s vooraleer je assistentie vraagt. Tip: gebruik een tabel van booleans.

Verdere tips voor een goede oplossing: