Eratostenovo sito

Iz Wikipedije, slobodne enciklopedije
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