Eratostenovo sito

Eratostenovo sito (tudi Eratostenovo rešeto) je preprost algoritem za iskanje vseh praštevil, manjših od izbranega števila. Pripisujejo ga grškemu matematiku, geografu in astronomu Eratostenu. Postopek poteka tako, da na papir napišemo vsa števila od 2 do izbranega, nato pa črtamo netrivialne mnogokratnike še neprečrtanih števil.

Za zgled si oglejmo iskanje praštevil, manjših od 20.

1. korak Izpišemo vsa števila, začenši z 2:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

2. korak Prvo število na seznamu označimo kot praštevilo.

Animacija Eratostenovega sita na prvih 120 naravnih številih

Znana praštevila: 2

Glavni seznam: 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

3. korak Iz glavnega seznama izločimo vsa števila, ki so mnogokratniki zadnjega števila dodanega na seznam praštevil.

Znana praštevila: 2

Glavni seznam: 3 5 7 9 11 13 15 17 19

4. korak Če je največje število na glavnem seznamu manjše od kvadrata največjega števila na seznamu praštevil, označimo vsa števila na glavnem seznamu kot praštevila, sicer pa se vrnemo na 2. korak.

Ker je 19 večje od 2² = 4, se vrnemo na 2. korak:

Znana praštevila: 2 3

Glavni seznam: 5 7 9 11 13 15 17 19

Ponovno 3. korak:

Znana praštevila: 2 3

Glavni seznam: 5 7 11 13 17 19

19 je večje od 3² = 9, zato se vrnemo na 2. korak:

Znana praštevila: 2 3 5

Glavni seznam: 7 11 13 17 19

3. korak ne spremeni nobenega od seznamov.

19 je manj kot 5² = 25, torej so vsa preostala števila na glavnem seznamu praštevila.

Rezultat: praštevila do 20 so: 2, 3, 5, 7, 11, 13, 17, 19.