Eratosteno rėtis

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką

Eratosteno rėtis. Graikų matematikas Eratostenas (~275-~195 m. pr. m. e.) pasiūlė paprastą metodą kaip rasti visus pirminius skaičius nuo 2 iki n. 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.

Metodas[taisyti | redaguoti kodą]

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