Zeef van Eratosthenes

Om te bepalen of een getal een priemgetal is, kan je de Zeef van Eratosthenes gebruiken. Om getallen te controleren kan 'Trial Division' worden gebruikt, hiermee weet je 100% zeker of een getal een priemgetal is. Het nadeel is dat 'Trial Division' is dat het arbeidsintensief is. Om dit proces te versnellen wordt de zeef van Eratosthenes gebruikt. Het controleren vindt niet meer plaats met alle getallen, maar alleen met priemgetallen.

Priemgetal

Een priemgetal is een natuurlijk getal groter dan 1, met precies twee delers. Het getal 21 heeft als delers 1, 3, 7 en 21. Met vier delers is het geen priemgetal. Het getal 23 heeft als delers 1 en 23. Met twee delers is het wel een priemgetal. Het getal 2 is de eerste priemgetal, met als delers 1 en 2. Omdat 2 een even getal is, zijn alle overige even getallen hierdoor geen priemgetallen. Alle even getallen zijn deelbaar door 2.

Alle delers proberen (Trial Division)

Om te controleren of een getal een priemgetal is, berekenen we het aantal delers. In onderstaande tabel controleren we de getallen 7, 9 11, 13, 15 en 17.

Tabel 1: de getallen delen van 1 tot en met het getal zelf

Later beginnen en eerder eindigen

Na het analyseren van tabel 1, is te zien dat 7, 11, 13 en 17 priemgetallen zijn. Deze hebben precies 2 delers. Er valt nog iets op. Zodra het resultaat van de deling onder de twee komt (9 : 5 = 1,8), wordt geen deler meer worden gevonden. Behalve het getal zelf. Daarbij is elk getal deelbaar door 1, deze controle vervalt dus.
Omdat bekend is of het getal even of oneven is, vervalt het delen door 2. Hierdoor beginnen we niet meer bij 1, maar bij 3. De controles vinden niet meer plaats t/m het getal, maar t/m de helft van het getal. Als de helft geen natuurlijk getal is, ronden we af naar beneden. We delen alleen door natuurlijke getallen en alle resultaten na het delen horen minimaal 2 te zijn.
De gegevens in tabel 1 wordt bijgewerkt met de nieuwe informatie, met onderstaande tabel als resultaat.

Tabel 2: delers beginnen bij 3 en eindigen voor de helft van het getal

Een aanname

Bij het analyseren van tabel 1 (of 2), valt nog iets op. Het moment dat bewezen wordt dat het getal geen priemgetal is. Een deler is gevonden wanneer de wortel van het getal is bereikt. Neem het getal 9, met als wortel 3. Wanneer we de deler 3 zijn, is bewezen dat het geen priemgetal is. Neem het getal 15, met als wortel 3,873. Ook bij het getal 15 is een deler (3) gevonden wanneer de wortel is bereikt.
We controleren het getal 2047, met als wortel 45,244. Bij het bereiken van de wortel, horen we te weten of het een priemgetal is. Zie onderstaande tabel met de resultaten.

Tabel 3: het vinden van de eerste deler van 2047

Het bewijs voor de maximale deler

Een deler is gevonden wanneer de wortel is bereikt, als het getal geen priemgetal is. Dit valt als volgt te bewijzen. Neem de formule: n = m x l. Met deze formule geldt het volgende: wanneer m groter wordt, wordt l kleiner. En andersom. Stel dat m en l gelijk zijn, dan is de maximale deler is nooit hoger dan de wortel.
Stel n is 16, met als wortel 4. In dit geval weten we dat 4 een deler is. Als de wortel niet de deler is, dan moet een van de delers lager (2) of hoger (8) zijn dan deze wortel. De gegevens in tabel 2 passen we aan met de nieuwe informatie en krijgen onderstaande tabel.

Tabel 4: de overgebleven stappen om te bepalen of het een priemgetal is

Voor de kleinere priemgetallen hebben we niet veel controles nodig, Voor het getal 7 is zelfs geen controle meer nodig.

Het toepassen van een zeef

Wanneer het getal niet deelbaar is door 2, moet dan ook gecontroleerd worden of het deelbaar is door 4, 6 of 8? Als het deelbaar is door 2, dan is het een even getal. Hierdoor hoef je niet te controleren of het deelbaar is door andere even getallen. Is het deelbaar is door 4, dan is het ook deelbaar door 2. Hetzelfde geldt voor 6 en 8. Is het deelbaar door 3, dan hoeven we niet te controleren of het ook deelbaar is door 6, 9 of 12. Hierdoor vallen stappen weg. Maar welke blijven over?
We gebruiken een tabel met de getallen 2 t/m 49. We nemen steeds het eerste getal en filteren de overige delers.

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	31	32	33	34	35	36
37	38	39	40	41	42	43
44	45	46	47	48	49

Tabel 5: de getallen 2 t/m 49 nu nog gebruikt als deler

We beginnen met 2, waarna we onderstaande tabel krijgen.

2	3	5	7	9	11	13
15	17	19	21	23	25	27
29	31	33	35	37	39	41
43	45	47	49

Tabel 6: de overgebleven delers na het filteren met 2

Het volgende getal is 3, na het filteren ziet de tabel er als volgt uit.

2	3	5	7	11	13	17
19	23	25	29	31	35	37
41	43	47	49

Tabel 7: de overgebleven delers na het filteren met 3

Het volgende getal is 5, na het filteren ziet de tabel er als volgt uit.

2	3	5	7	11	13	17
19	23	29	31	37	41	43
47	49

Tabel 8: de overgebleven delers na het filteren met 5

Het volgende getal is 7, na het filteren ziet de tabel er als volgt uit.

2	3	5	7	11	13	17
19	23	29	31	37	41	43
47

Tabel 9: de overgebleven delers na het filteren met 7

Priemgetallen als deler

Wat valt op aan de getallen in tabel 9? De overgebleven getallen zijn priemgetallen. Om sneller priemgetallen te vinden, heb je andere priemgetallen nodig.
We controleren 2047 nog een keer. In tabel 3 is na 21 delers bewezen dat 2047 geen priemgetal is. Door gebruik te maken van de zeef, blijven de volgende delers over: 3, 5, 7, 11, 13, 17, 19 en 23. Een verschil van dertien delers.

Bronnen

• PrimePages, The Prime Glossary: trial division, Retrieved 10:28, October 20, 2020, from https://primes.utm.edu/glossary/page.php?sort=TrialDivision
• Weisstein, Eric W. 'Natural Number.' From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/NaturalNumber.html
• Is 1 prime?., Brilliant.org. Retrieved 09:34, February 23, 2019, from https://brilliant.org/wiki/is-1-prime/
• Horsley, S (1772)., The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, pp. 327-347
• O'Neill, M., The Genuine Sieve of Eratosthenes https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf