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

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

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

Ալգորիթմ

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

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

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

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

Բարդության ապացույց 
Ընտրված  թվի համար ամեն պարզ  թվի համար կատարվում է ներքին ցիկլ(կրկնություն), որը կկատարի  գործողություն։ Հետևաբար, պետք է գնահատել հետևյալ մեծությունը՝

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

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

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

Ավելի խիստ և հիմնավորված ապացույց հնարավոր է գտնել 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 դեպքի համար 
Գրենք -ից մինչև  եղած բոլոր բնական թվերը՝

 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
 Доказательство сложности алгоритма
 Еще раз о поиске простых чисел

Ալգորիթմներ