Eratosteno rėtis metodas rasti visus pirminius skaičius nuo 2 iki n pasiūlytas graikų matematiko Eratosteno 275 195 m pr

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.

Šiuolaikinėje matematikoje Eratosteno rėčio idėja remiamasi nagrinėjant pirminių skaičių ir kitas problemas, tai vadinamieji rėčio metodai.

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

V. Dagienė, G. Grigas, K. Augutis. Šimtas programavimo uždavinių. Šviesa, 1986. 223 p. (yra algoritmas Pascal kalba)
K.Bulota, P.Survila. Algebra ir skaičių teorija. II dalis. – Vilnius: Mokslas, 1990. – 39 p. ISBN 5-420-00613-8

Šis su matematika susijęs straipsnis yra nebaigtas. Jūs galite prisidėti prie Vikipedijos papildydami šį straipsnį.

[grigas-1] V. Dagienė, G. Grigas, K. Augutis. Šimtas programavimo uždavinių. Šviesa, 1986. 223 p. (yra algoritmas Pascal kalba)

[2] K.Bulota, P.Survila. Algebra ir skaičių teorija. II dalis. – Vilnius: Mokslas, 1990. – 39 p. ISBN 5-420-00613-8