Eratostenovo sito

Izvor: Wikipedia
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