Eratosteno rėtis

Eratosteno rėtis – metodas rasti visus pirminius skaičius nuo 2 iki n, pasiūlytas graikų matematiko Eratosteno (~275-~195 m. pr. m. e.). Jis ant papiruso surašė visus natūrinius skaičius nuo 2 iki 1000 ir pradurdavo sudėtinius skaičius. Tokiu būdu liko tarsi rėtis su „išsijotais“ sudėtiniais skaičiais, o pirminiai skaičiai liko.V. Dagienė, G. Grigas, K. Augutis. Šimtas programavimo uždavinių. Šviesa, 1986. 223 p. (yra algoritmas Pascal kalba)

Šiuolaikinėje matematikoje Eratosteno rėčio idėja remiamasi nagrinėjant pirminių skaičių ir kitas problemas, tai vadinamieji rėčio metodai.K.Bulota, P.Survila. Algebra ir skaičių teorija. II dalis. – Vilnius: Mokslas, 1990. – 39 p. ISBN 5-420-00613-8

 Metodas 
Pirmiausia – surašomi visi skaičiai nuo 2 iki n:

 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Skaičius 2 pirminis, taigi perbraukiame visus didesnius skaičius, kurie dalijasi iš 2, t. y. kas antrą:

 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Toliau imame kitą neužbrauktą skaičių ir išbraukiame visus jo kartotinius. Taip kartojame ir gauname:

 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

 Šaltiniai 

Kategorija:Skaičių teorija