Eratostenovo sito predstavlja postupak kojim se izdvajaju prosti brojevi manji od nekog zadatog broja.
Šta su to prosti brojevi?
PROSTI BROJEVI su brojevi koji se mogu podeliti samo jedinicom i samim sobom.
Prikazaćemo postupak kako da odredimo sve proste brojeve manje od 120 koristeći Eratostenovo sito.
Napišemo brojeve od 2 do 120.
- Prvi prost broj je broj 2. Precrtamo sve brojeve deljive sa 2 (parne brojeve).
- Sledeći broj na spisku je broj tri. I on je prost broj. Sa spiska precrtavamo brojeve deljive sa tri koje već nismo precrtali 9,15,21,27,…
- Sledeći broj na spisku je broj pet. I to je prost broj. Sa spiska precrtavamo 25,35,55,65,85,95,115…
- Sledeći na spisku je broj sedam. U spisku prostih brojeva imamo za sada 2,3,5 i 7. Precrtavamo sa spiska 49, 77, 91 i 119, tj. brojeve deljive sa sedam. Napomena: 56, 63, 70, 84, 98, 105 i 112 su već ranije precrtani.
- Sledeći broj je 11. Kako je 11×11 > 120 to obeležavamo da su svi preostali brojevi prosti.To su 11, 13, 17, 19, 23, 29, 31, 37, …
