Էրատոսթենեսի մաղ

Էրատոսթենեսի մաղ
Տեսակ	primality test?
Անվանված է	Էրատոսթենես Կիրենացի

Էրատոսթենեսի մաղ մինչև $n$ որոշակի ամբողջ թիվը եղած պարզ թվերը գտնելու ալգորիթմ, որի հայտագործումը վերագրում են հին հույն մաթեմատիկոս Էրատոսթենես Կիրենացուն^[1]։ Ինչպես և մնացած բոլոր դեպքերում, այստեղ ալգորիթմի անունը խոսում է նրա կատարած աշխատանքի սկզբունքի մասին, այսինքն մաղը իրենից ենթադրում է «զտում», այս դեպքում, բացի պարզ թվերից, «զտվում են» մնացած բոլոր թվերը։ Թվերի ցանկով առաջ անցնելիս պարզ թվերը մնում են, իսկ մնացած թվերը, որոնք կոչվում են բաղադրյալ թվեր, հեռացվում են։

Պատմություն

Համաձայն լեգենդի, մեթոդը ստացել է «մաղ» անվանումը, քանի որ Էրատոսթենեսը թվերը գրում էր մոմով պատված փոքրիկ տախտակի վրա, և անցք էր բացում այն տեղերում, որտեղ գրված էին բաղադրյալ թվեր։ Տախտակը նմանեցնում էին մաղի, որի միջոցով մաղում էին բաղադրյալ թվերը և թողնում միայն պարզ թվերը։ Էրատոսթենեսը կազմել է մինչև 1000 եղած պարզ թվերի ցանկը։

Ալգորիթմ

Մինչև տրված n թիվը եղած պարզ թվերը գտնելու համար, համաձայն Էրատոսթենեսի մեթոդի, անհրաժեշտ է կատարել հետևյալ քայլերը՝

Գրել 2-ից մինչև n թիվը եղած բոլոր ամբողջ թվերը (2, 3, 4, …, n)։
Ներմուծել p փոփոխականը, որը հավասար է առաջին պարզ թվին՝ 2-ի։
Ընդգծել 2p-ից մինչև n եղած թվերը, արժեքը ավելացնելով p-ով (ցանկը կլինի հետևյալը՝ p, 2p, 3p, 4p, …)։
Գտնել առաջին p-ից մեծ արժեք ունեցող չընդգծված թիվը, և p փոփոխականին տալ նրա արժեքը։
Քանի հնարավոր է կրկնել 3-րդ և 4-րդ քայլերը։

Հիմա 2-ից միինչև n եղած բոլոր չընդգծված թվերը պարզ են։

Գործնականում ալգորիթմը հնարավոր է հեշտացնել հետևյալ ձևով. 3-րդ քայլում թվերը ընդգծել սկսած p²-ից, քանի որ դրանից փոքր բոլոր բաղադրյալ թվերը այդ ժամանակ ընդգծված չեն լինում։ Եվ, համապատասխանաբարորեն ալգորիթմի քայլերը դադարեցնել երբ p²-ը դառնա p-ից մեծ։ Ինչպես նաև, բոլոր պարզ թվերը(բացի 2-ից) կենտ են, այդ իսկ պատճառով, նրանց կարելի է հաշվել 2p քայլով , սկսած p²-ից։

Ալգորիթմի բարդություն

Մինչև $n$ եղած պարզ թվերը հաշվելու ալգորիթմի հաշվողական բարդությունը $O(n\log(\log n))$ է^[2]։

Բարդության ապացույց

Ընտրված $n\in \mathbb {N}$ թվի համար ամեն պարզ $p\in \mathbb {P} \colon p\leq n$ թվի համար կատարվում է ներքին ցիկլ(կրկնություն), որը կկատարի ${\frac {n}{p}}$ գործողություն։ Հետևաբար, պետք է գնահատել հետևյալ մեծությունը՝

$\sum \limits _{p\in \mathbb {P} \colon p\leq n}{\frac {n}{p}}=n\cdot \sum \limits _{p\in \mathbb {P} \colon p\leq n}{\frac {1}{p}}$

Քանի որ $n$ -ից փոքր կամ հավասար պարզ թվերի քանակը գնահատվում է որպես ${\frac {n}{\ln n}}$ , ինչի արդյունքում, $k$ պարզ թիվը մոտավորապես հավասար է $k\ln k$ , գումարը հնարավոր է գրել այսպես՝

$\sum \limits _{p\in \mathbb {P} \colon p\leq n}{\frac {1}{p}}\approx {\frac {1}{2}}+\sum \limits _{k=2}^{\frac {n}{\ln n}}{\frac {1}{k\ln k}}$

Այստեղ գումարից առանձնացվում է առաջին պարզ թիվը, որպեսզի խուսափենք 0 թվի վրա բաժանելուց։ Այսպիսով գումարը հնարավոր է գնահատել հետևյալ ինտեգրալով՝

${\frac {1}{2}}+\sum _{k=2}^{\frac {n}{\ln n}}{\frac {1}{k\ln k}}\approx \int \limits _{2}^{\frac {n}{\ln n}}{\frac {1}{k\ln k}}\,dk=\ln \ln k{\Bigr |}_{2}^{\frac {n}{\ln n}}=\ln \ln {\frac {n}{\ln n}}-\ln \ln 2=\ln(\ln n-\ln \ln n)-\ln \ln 2\approx \ln \ln n$

Արդյունքում ստանում ենք հետևյալը՝

$\sum \limits _{p\in \mathbb {P} \colon p\leq n}{\frac {n}{p}}\approx n\ln \ln n+o(n)$

Ավելի խիստ և հիմնավորված ապացույց հնարավոր է գտնել Hardy и Wright «An Introduction to the Theory of Numbers» գրքում^[3]։

Մեքենայական կոդ

Մեքենայական օպտիմալ կոդի իրագործված է հետևյալ կերպ^[4]^[5]՝

Մուտք։ n բնական թիվ

A — տրամաբանական(բինար) զանգված, ինդեքսավորված 2-ից մինչև  n,սկզբնապես արժևորված true արժեքով։

for i := 2, 3, 4, ..., while i ≤ n:
 if A[i] = true:
for j := i², i² + i, i² + 2i, ..., while j ≤ n:
 A[j] := false

Ելք։ i թվեր, որոնց համար A[i] = true

Օրինակ n = 30 դեպքի համար

Գրենք $2$ -ից մինչև $30$ եղած բոլոր բնական թվերը՝

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Ցանկում առաջին թիվը՝ $2$ ը պարզ թիվ է։ Անցնելով ցանկով, ջնջենք $2$ ին պատիկ բոլոր թվերը(այսինքն ամեն երկրորդը, սկսած $22 = 4$ -ից )

2 3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Մյուս չջնջված թիվը՝ $3$ ը պարզ է։ Անցնելով ցանկով, ջնջենք $3$ ին պատիկ բոլոր թվերը(այսինքն ամեն երկրորդը, սկսած $32 = 9$ -ից )

2 3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Մյուս չջնջված թիվը՝ $5$ ը պարզ է։ Անցնելով ցանկով, ջնջենք $5$ ին պատիկ բոլոր թվերը(այսինքն ամեն երկրորդը, սկսած $52 = 25$ -ից ) և այսպես շարունակ՝

2 3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Մյուս չջնջված թիվը՝ $7$ , նրա քառակուսին՝ $49$ ավելի մեծ է քան $30$ -ը, այսինքն աշխատանքը ավարտված է և պարզ թվերի ցանկը հետևյալն է՝

2 3 5 7  11  13   17  19   23 29

Ծանոթագրություններ

↑ Никомах Герасский, Введение в арифметику, I, 13. [1]
↑ Волшебное решето Эратосфена
↑ Hardy and Wright "An Introduction to the Theory of Numbers, p. 349
↑ Sedgewick, Robert (1992). Algorithms in C++. Addison-Wesley. ISBN 0-201-51059-6. Վերցված է 2011 թ․ հոկտեմբերի 26-ին., p. 16.
↑ Jonathan Sorenson, An Introduction to Prime Number Sieves, Computer Sciences Technical Report #909, Department of Computer Sciences University of Wisconsin-Madison, January 2 1990 (the use of optimization of starting from squares, and thus using only the numbers whose square is below the upper limit, is shown).

Գրականություն

Гальперин Г. «Просто о простых числах» // Квант. — № 4.
Под. ред. Невская И.И. Неопубликованные материалы Л.Эйлера по теории чисел. — "Наука", 1997.(չաշխատող հղում)
Проф. Д.Ф.Егоров Элементы теории чисел. — Государственное издательство Москва, 1923.
Кордемский Б. А. Математическая смекалка. — М.: ГИФМЛ, 1958. — 576 с.

Արտաքին հղումներ

[1] Никомах Герасский, Введение в арифметику, I, 13. [1]

[2] Волшебное решето Эратосфена

[3] Hardy and Wright "An Introduction to the Theory of Numbers, p. 349

[sedgewick-4] Sedgewick, Robert (1992). Algorithms in C++. Addison-Wesley. ISBN 0-201-51059-6. Վերցված է 2011 թ․ հոկտեմբերի 26-ին., p. 16.

[intro-5] Jonathan Sorenson, An Introduction to Prime Number Sieves, Computer Sciences Technical Report #909, Department of Computer Sciences University of Wisconsin-Madison, January 2 1990 (the use of optimization of starting from squares, and thus using only the numbers whose square is below the upper limit, is shown).

[1]

[2]

[3]

[4]

[5]