title: Zeef van Eratosthenes
text: 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 zij 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
  Maak een gesorteerde lijst van alle getallen van 2 tot een zelf te kiezen maximum.
  Kies het kleinste getal uit de lijst.
  Streep alle veelvouden van het gekozen getal door (maar niet het getal zelf).
  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
  
  Overblijvende getallen
  Na het wegstrepen van de veelvouden van 2 blijft vanaf het getal 3 van elke 2 opeenvolgende getallen 1 over.
  Na het ook wegstrepen van de veelvouden van 3 blijven vanaf het getal 4 van elke 6 opeenvolgende getallen 2 over.
  Na het ook wegstrepen van de veelvouden van 5 blijven vanaf het getal 6 van elke 30 opeenvolgende getallen 8 over.
  Na het ook wegstrepen van de veelvouden van 7 blijven vanaf het getal 8 van elke 210 opeenvolgende getallen 48 over.
  
  Het aantal, vanaf het getal 8, dat van elke 210 opeenvolgende getallen overblijft, is dus respectievelijk 105, 70, 56 en 48, een vermindering van respectievelijk een fractie 1/2, 1/3, 1/5 en 1/7 ten opzichte van het in de vorige stap overgebleven aantal, beginnend met het aantal 210.
  
  Tot 220 zijn er 47 priemgetallen: de getallen 2, 3, 5 en 7, en van de 48 overgebleven getallen tussen 10 en 220 zijn 121, 143, 169, 187, 209 geen priemgetallen.
  
  Algoritme
  Priemgetal
  Priemgetaltest
  Zeeftheorie