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

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

Պատմություն

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

Ալգորիթմ

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

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

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

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

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

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

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

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

$\sum _{p\in \mathbb{P}:p\le n}\frac{n}{p}=n\cdot \sum _{p\in \mathbb{P}:p\le n}\frac{1}{p}$

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

$\sum _{p\in \mathbb{P}:p\le n}\frac{1}{p}\approx \frac{1}{2}+\sum _{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 \underset{2}{\overset{\frac{n}{\ln n}}{\int }}\frac{1}{k\ln k}dk=\ln \ln k{|}_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 _{p\in \mathbb{P}:p\le n}\frac{n}{p}\approx n\ln \ln n+o(n)$

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

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

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

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

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

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

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

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

Գրենք Կաղապար:Math-ից մինչև Կաղապար:Math եղած բոլոր բնական թվերը՝

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

Ցանկում առաջին թիվը՝ Կաղապար:Mathը պարզ թիվ է։ Անցնելով ցանկով, ջնջենք Կաղապար:Mathին պատիկ բոլոր թվերը(այսինքն ամեն երկրորդը, սկսած Կաղապար:Math-ից )

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

Մյուս չջնջված թիվը՝Կաղապար:Mathը պարզ է։ Անցնելով ցանկով, ջնջենք Կաղապար:Mathին պատիկ բոլոր թվերը(այսինքն ամեն երկրորդը, սկսած Կաղապար:Math-ից )

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

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

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

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

2 3 5 7  11  13   17  19   23 29

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

• Կաղապար:Ռուսերեն հոդված
• Կաղապար:Ռուսերեն գիրքԿաղապար:Չաշխատող արտաքին հղում
• Կաղապար:Ռուսերեն գիրքԿաղապար:Չաշխատող արտաքին հղում
• Կաղապար:Ռուսերեն գիրք

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

• Решето Эратосфена от М. Гарднера
• Алгоритм составления таблицы простых чисел от заданного до другого числа
• Реализация алгоритма поиска простых чисел на Java
• Доказательство сложности алгоритма
• Еще раз о поиске простых чисел