De zeef van Eratosthenes: Het algoritme wordt gebruikt om de priemgetallen in een lijst te vinden (identificeren). Tip: begin met het doorstrepen van de veelvouden van de kleinere priemgetallen

De Griekse wiskundige Eratosthenes (275 - 194 v. Chr.) gebruikte een nieuwe en eenvoudige methode om te bepalen of de getallen in een lijst priemgetallen zijn of niet.
Hij begon met de bekende kleine priemgetallen 2, 3, 5, 7, 11, 13, 17, 23, etc. Het is duidelijk dat al hun veelvouden geen priemgetallen zijn maar samengestelde.

Hij rangschikte een lijst met natuurlijke getallen in oplopende volgorde. Vervolgens identificeerde en verwijderde hij alle grotere samengestelde getallen in deze lijst, aangezien het veelvouden zijn van de eerste priemgetallen, waardoor de grotere priemgetallen in deze lijst apart worden gezet.
We illustreren deze methode hieronder, met een lijst met getallen gesorteerd in oplopende volgorde, van 2 tot 100:

Het getal 2 is een priemgetal, dus identificeren we eerst alle veelvouden van 2 in de lijst:
2 × 2 = 4
2 × 3 = 6
2 × 4 = 8
2 × 5 = 10
2 × 6 = 12
2 × 7 = 14
2 × 8 = 16
2 × 9 = 18
2 × 10 = 20
... enzovoort, tot het getal: 2 × 50 = 100.
Het getal 2 × 51 = 102, is groter dan 100, dus we kunnen stoppen.
Verwijder alle veelvouden van het getal 2 uit de lijst: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100.

Het getal 3 is een priemgetal, dus identificeren we alle veelvouden van 3 in de lijst:
3 × 2 = 6 (Dit getal is al uit de lijst gehaald, het is een veelvoud van 2);
3 × 3 = 9
3 × 4 = 12 (Dit getal is al uit de lijst gehaald, het is een veelvoud van 2);
3 × 5 = 15
3 × 6 = 18 (Dit getal is al uit de lijst gehaald, het is een veelvoud van 2);
... enzovoort, tot het getal: 3 × 33 = 99.
Het getal 3 × 34 = 102, is groter dan 100, dus we kunnen stoppen.
Verwijder alle veelvouden van het getal 3 uit de lijst: 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 97, 99.
Als we alle veelvouden van het getal 2 al uit de lijst hebben gehaald, houden we alleen nog over: 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93. 99. Deze getallen staan hieronder, als veelvouden van het getal 3:
3 × 3 = 9
3 × 5 = 15
3 × 7 = 21
3 × 9 = 3 × 3 × 3 = 27
3 × 11 = 33
3 × 13 = 39
3 × 15 = 3 × 3 × 5 = 45
3 × 17 = 51
3 × 19 = 57
3 × 21 = 3 × 3 × 7 = 63
3 × 23 = 69
3 × 25 = 3 × 5 × 5 = 75
3 × 27 = 3 × 3 × 3 × 3 = 81
3 × 29 = 87
3 × 31 = 93
3 × 33 = 3 × 3 × 11 = 99.

We gaan dan verder met het volgende priemgetal, 5:
5 × 2 = 10 (Dit getal is al uit de lijst verwijderd - het is een veelvoud van 2);
5 × 3 = 15 (Dit getal is al uit de lijst verwijderd - het is een veelvoud van 3);
5 × 4 = 20 (Dit getal is al uit de lijst verwijderd - het is een veelvoud van 2);
5 × 5 = 25
5 × 6 = 30 (Dit getal is al uit de lijst verwijderd - het is een veelvoud van 2 en 3);
5 × 7 = 35
... enzovoort, tot het getal: 5 × 20 = 100 (Dit getal is al uit de lijst verwijderd - het is een veelvoud van 2).
Het getal 5 × 21 = 105, is groter dan 100, dus we kunnen stoppen.
Verwijder alle veelvouden van het getal 5 uit de lijst: 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100.
Als we niet letten op de veelvouden van 2 en 3, die al uit de lijst zijn verwijderd, houden we nog steeds deze getallen over om te verwijderen: 25, 35, 55, 65, 85, 95, ... precies die getallen die in hun priemontbinding alleen priemfactoren groter dan of gelijk aan 5 hebben:
5 × 5 = 25
5 × 7 = 35
5 × 11 = 55
5 × 13 = 65
5 × 17 = 85
5 × 19 = 95.

Daarna herhalen we het proces met het volgende priemgetal 7:
7 × 2 = 14 (het nummer is al uit de lijst verwijderd - het is een veelvoud van 2);
7 × 3 = 21 (het nummer is al uit de lijst verwijderd - het is een veelvoud van 3);
7 × 4 = 28 (het nummer is al uit de lijst verwijderd - het is een veelvoud van 2);
7 × 5 = 35 (het nummer is al uit de lijst verwijderd - het is een veelvoud van 5);
7 × 6 = 42 (het nummer is al uit de lijst verwijderd - het is een veelvoud van 2 en 3);
7 × 7 = 49
... enzovoort, tot het getal: 7 × 14 = 98 (het nummer is al uit de lijst verwijderd - het is een veelvoud van 2).
7 × 15 = 105, is groter dan 100, dus we kunnen stoppen.
Verwijder alle veelvouden van het getal 7 uit de lijst: 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98.
Als we niet letten op de veelvouden van 2, 3 en 5, die al uit de lijst zijn verwijderd, moeten we nog steeds verwijderen: 49, 77, 91. Dit zijn precies de getallen die in hun priemontbinding priemfactoren hebben die groter zijn dan of gelijk zijn aan 7:
7 × 7 = 49
7 × 11 = 77
7 × 13 = 91.

Het volgende priemgetal in de lijst is 11 en we moeten de veelvouden van 11 uit de lijst verwijderen.
Zoals we in de bovenstaande stappen hebben gezien, moeten we echter alleen proberen die getallen uit de lijst te verwijderen die in hun ontbindingsfactoren priemfactoren hebben die groter zijn dan of gelijk zijn aan 11.
Maar al 11 × 11 = 121, wat groter is dan 100.
Dit betekent dat alle getallen die na het uitvoeren van de bovenstaande stappen in de lijst zijn achtergebleven al priemgetallen zijn.

De lijst met priemgetallen bestaat uit de niet-verwijderde getallen.
Nadat we alle veelvouden van de priemgetallen 2, 3, 5 en 7 uit de lijst hebben verwijderd, blijven we in de lijst achter met deze getallen: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 - de lijst met priemgetallen van 2 tot 100.

Enkele artikelen over de priemgetallen