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

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

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

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

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

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

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

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

 \sum\limits_{p\in \mathbb{P}\colon p \le n} {\frac{n}{p}} = n\cdot\sum\limits_{p\in \mathbb{P}\colon p \le n} {\frac{1}{p}} 

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

 \sum\limits_{p \in \mathbb{P}\colon p \le 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^{\frac{n}{\ln n}}_{k=2}{\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 \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* &le; *n*:
  **if** *A*[*i*] = **true**:
 **for** *j* := *i*2, *i*2 + *i*, *i*2 + 2*i*, ..., **while** *j* &le; *n*:
  *A*[*j*] := **false**
 
 **Ելք**։ *i* թվեր, որոնց համար *A*[*i*] = **true**

## Օրինակ n = 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 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 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 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 3 5 7  11  13   17  19   23 29

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

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

## Արտաքին հղումներ
* Решето Эратосфена от М. Гарднера
* Алгоритм составления таблицы простых чисел от заданного до другого числа
* Реализация алгоритма поиска простых чисел на Java
* Доказательство сложности алгоритма
* Еще раз о поиске простых чисел

Կատեգորիա:Ալգորիթմներ