Eratostenovo sito

Iz Wikipedije, proste enciklopedije

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 večkratnike š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.

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 večkratniki 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.