Zeef van Eratosthenes

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.

Animatie van de toepassing van de zeef van Eratosthenes op de gehele getallen van 1 t/m 120.

Methode

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

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

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.