Eratostenovo sito je postupak za pronalaženje prostih (primarnih) brojeva – cijelih brojeva djeljivih samo sa sobom i sa 1. (Broj 1, po definiciji, ne spada u proste brojeve.) Ovaj postupak uključuje filtriranje neprostih brojeva s popisa svih brojeva od 2 do bilo koje gornje granice.
Evo kako pronaći proste brojeve do 50:
- Napišite sve brojeve od 2 do 50.
- Zaokružite 2, a zatim prekrižite sve sadržioce broja 2 (4, 6, 8 itd.).
- Zaokružite sljedeći neprekriženi broj i zatim prekrižite sve njegove sadržioce.
- Ponovite korak 3 dok ne dođete do kraja popisa.
- Prosti brojevi su zaokruženi brojevi, a prekriženi brojevi nisu prosti.
