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 verwijderen we alle veelvouden van 3.
- Herhaal de werkwijze en klik steeds het eerstvolgende nog overblijvende getal aan.