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 večkratnike še neprečrtanih števil.
Zgled
[uredi | uredi kodo]Za zgled si oglejmo iskanje praštevil, manjših od 30.
Najprej ustvarimo seznam števil od 2 do 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
Začnemo s številom 2, prvo številko na seznamu. Prečrtamo vse njene večkratnike, torej vsa števila, ki jih dobimo z dodajanjem 2 (4, 6, 8, ...):
2 3456789101112131415161718192021222324252627282930
Nato nadaljujemo s številom 3, prvim neprečrtanim številom. Prečrtamo vse njene večkratnike, torej števila, ki jih dobimo z dodajanjem 3 (6, 9, 12, ...):
2 3456789101112131415161718192021222324252627282930
Naslednje neprečrtano število je 5. Prečrtamo vse njene večkratnike (10, 15, 20, ...):
2 3456789101112131415161718192021222324252627282930
Naslednje še ne prečrtano število na seznamu je 7; naslednji korak bi bil prečrtati vse njene večkratnike, vendar so na tej točki vsa že prečrtana, saj so ta števila (14, 21, 28) tudi večkratniki manjših praštevil, ker je 7 × 7 večje od 30. Ker je največje število na seznamu (30) manjše od kvadrata števila 7 (49), lahko vsa neprečrtana števila označimo kot praštevila. Ta števila so vsa praštevila pod 30:
2 3 5 7 11 13 17 19 23 29