Zeef van Eratosthenes

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Animatie van de toepassing van de zeef van Eratosthenes op de gehele getallen van 1 t/m 120.

De zeef van Eratosthenes (bibliothecaris van Alexandrië vanaf ca. 240 v.Chr.) is een al zeer lang bekend algoritme om priemgetallen te vinden. Deze elegante methode is vooral efficiënt wanneer hij wordt gebruikt voor de kleinere priemgetallen. De methode vergt echter het bijhouden van alle getallen kleiner dan de gebruikte bovengrens, wat naarmate de te bepalen priemgetallen groter worden een steeds groter nadeel wordt.

Methode[bewerken]

  1. Maak een gesorteerde lijst van alle getallen van 2 tot een zelf te kiezen maximum.
  2. Kies het kleinste getal uit de lijst.
  3. Streep alle veelvouden van het gekozen getal door (maar niet het getal zelf).
  4. Kies het volgende getal uit de lijst en ga verder met stap 3.

De getallen die op deze manier overblijven zijn alle priemgetallen tot het maximum.

De procedure kan op enkele manieren versneld worden.

  • Het heeft geen zin in stap 4 een getal te kiezen dat al doorgestreept is, want alle veelvouden daarvan zijn al doorstreept.
  • Men kan met doorstrepen beginnen met het kwadraat van het gekozen getal. Alle kleinere veelvouden zijn al doorstreept.
  • Is het gekozen getal groter dan de wortel uit het maximum, dan is de procedure voltooid.

Voorbeeld[bewerken]

We zoeken bijvoorbeeld de priemgetallen tot en met 30. We beginnen met de lijst van 2 tot en met 30 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
In de eerste ronde strepen we de veelvouden van 2 weg, te beginnen met 22, dus 4 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29
Daarna gaan we verder met de veelvouden van 3, te beginnen met 32, dus 9 (de grijze vakjes zijn veelvouden van 3 die minder zijn dan 9, deze kunnen we negeren) 2 3 5 7 11 13 17 19 23 25 29
Het getal 4 is al weggestreept, dus gaan we verder met veelvouden van 5, te beginnen met 52, dus 25. 2 3 5 7 11 13 17 19 23 29
Het volgende getal is 7, dus moeten we nu de veelvouden van 7 wegstrepen, te beginnen met 72, maar dat is meer dan 30, dus we kunnen nu stoppen. Wat we overhouden zijn de priemgetallen met een maximum van 30: 2 3 5 7 11 13 17 19 23 29