Python: de zeef van Eratosthenes

De zeef van Eratosthenes  (Bibliothecaris van de bibliotheek van Alexandrië rond 240 v.C.) is een algoritme om priemgetallen te bepalen kleiner dan een gegeven getal n:

  • Maak een geordende lijst van alle getallen van 2 tot n.
  • Neem het kleinste getal in deze lijst en schrap alle veelvouden van dit getal ( het getal zelf niet!).
  • Neem het volgende getal in de lijst en doe hiervoor hetzelfde.

Een programma in Python geeft bijvoorbeeld alle priemgetallen kleiner dan 50

:

Uitleg: 

  • Neem een lijst van lengte n en zet op elke plaats de boolse waarde True.
  • Begin met p=2 en zet alle veelvouden van 2 in de lijst op False. Begin met het eerste veelvoud van 2 na 2 zelf: dat is 2*2.
  • Neem dan p=3 en zet alle veelvouden van 3 op False, beginnend met 3*3 
    (want alle vroegere veelvouden zijn sowieso al op False gezet.
  • Doe zo verder zolang p*p kleiner is dan de gegeven waarde n.