Eratostenovo sito

Način dobivanja prostih brojeva pomoću Eratostenovog sita

Eratostenovo sito (rešeto) je jednostavan algoritam za dobivanje svih prostih brojeva manjih od onog izabranog. Osmislio ga je grčki matematičar, geograf i astronom Eratosten.

Postupak dobivanja prostih brojeva pomoću Eratostenovog sita:

1. na papir napišemo sve brojeve od 2 do izabranoga, pa križamo sve višekratnike broja 2
2. križamo drugi prosti broj po redu – broj 3, a zatim sve njegove višekratnike
3. isti postupak ponovimo s brojem 5
4. isti postupak ponovimo s brojem 7
5. svi brojevi koji su ostali su prosti brojevi