Priemgetallen — natuurlijke getallen die enkel deelbaar zijn door 1 en zichzelf — zijn belangrijk in onze huidige wereld van beveiliging. Er bestaan programma’s om grote priemgetallen te zoeken. In augustus 2019 was het grootst gekende priemgetal gelijk aan \(2^{82589933} - 1\), een getal van bijna 25 miljoen cijfers. De zoektocht naar priemgetallen startte al in de oudheid bij de Grieken. De geleerde Eratosthenes vond al voor het begin van onze jaartelling een methode om priemgetallen te vinden. Vandaag kennen we deze methode als de zeef van Eratosthenes.

Schrijf een programma dat via deze methode de priemgetallen vindt die kleiner zijn dan 1000.

Hoe werkt de zeef?

Het idee is om systematisch alle veelvouden weg te strepen:

1. Maak een bool-array met een vakje voor elk getal van 0 tot 999. Elk vakje zegt: “is dit getal (voorlopig) een priemgetal?”. Begin door alle getallen vanaf 2 als priem te beschouwen (true); 0 en 1 zijn geen priemgetallen (false).
2. Neem het eerste getal dat nog als priem gemarkeerd staat (dat is 2). Streep alle veelvouden ervan weg (4, 6, 8, …) door hun vakje op false te zetten: een veelvoud van 2 kan immers geen priemgetal zijn.
3. Ga naar het volgende getal dat nog op true staat (3) en streep opnieuw al zijn veelvouden weg. Herhaal dit.
4. Wat overblijft op true, zijn precies de priemgetallen.

Een bool-array maak je net zoals een int-array, maar dan met het type bool: bool[] isPriem = new bool[1000];. Elk element is dan true of false. De index van het vakje stelt hier het getal zelf voor, zodat je rechtstreeks isPriem[getal] kan gebruiken.

Uitvoer

Toon alle gevonden priemgetallen kleiner dan 1000 op één regel, van elkaar gescheiden door een spatie en in oplopende volgorde.

Uitvoer (begin en einde):

2 3 5 7 11 13 17 19 23 ... 977 983 991 997

De eerste priemgetallen zijn dus 2 3 5 7 11 13 ... en het grootste priemgetal kleiner dan 1000 is 997.