De zeef van Eratosthenes
De zeef van Eratosthenes
Er bestaat geen formule die de priemgetallen genereert. Je kunt natuurlijk één na één onderzoeken of een geheel getal delers heeft om zo enkel de priemgetallen over te houden. Eratosthenes bedacht een praktische methode door omgekeerd te redeneren.
Vermits een priemgetal enkel deelbaar is door 1 en zichzelf, kunnen we alle veelvouden van getallen schrappen. De lijst met getallen aflopen van klein naar groot en telkens alle veelvouden schrappen ('te zeven') is veel gemakkelijker dan steeds grotere getallen te controleren op delers. Onderstaand applet toont hoe de methode werkt voor de getallen van 1 tot 100.
- 1 is geen priemgetal.
- Klik op het volgende getal in de tabel: 2. We verwijderen nu alle veelvouden van 2.
- Het eerstvolgende overblijvende getal in de tabel is 3. Het is niet deelbaar door 2 en is dus een priemgetal. Nu schrappen we alle veelvouden van 3. We herhalen de werkwijze en klikken steeds het eerstvolgende nog overblijvende getal aan.
- Nadat je de eerste rij opgekuist hebt en alle veelvouden van de getallen van 2 tot 10 verwijderd werden, vervolledigt het applet de tabel zodat enkel nog de priemgetallen tussen 1 en 100 overblijven.