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

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search
Էրատոսթենեսի մաղ
Տեսակprimality test
Անվանված էԷրատոսթենես Կիրենացի

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

Պատմություն[խմբագրել | խմբագրել կոդը]

Համաձայն լեգենդի, մեթոդը ստացել է «մաղ» անվանումը, քանի որ Էրատոսթենեսը թվերը գրում էր մոմով պատված փոքրիկ տախտակի վրա, և անցք էր բացում այն տեղերում, որտեղ գրված էին բաղադրյալ թվեր։ Տախտակը նմանեցնում էին մաղի, որի միջոցով մաղում էին բաղադրյալ թվերը և թողնում միայն պարզ թվերը։ Էրատոսթենեսը կազմել է մինչև 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-րդ քայլում թվերը ընդգծել սկսած p2-ից, քանի որ դրանից փոքր բոլոր բաղադրյալ թվերը այդ ժամանակ ընդգծված չեն լինում։ Եվ, համապատասխանաբարորեն ալգորիթմի քայլերը դադարեցնել երբ p2-ը դառնա p-ից մեծ։ Ինչպես նաև, բոլոր պարզ թվերը(բացի 2-ից) կենտ են, այդ իսկ պատճառով, նրանց կարելի է հաշվել 2p քայլով , սկսած p2-ից։

Ալգորիթմի բարդություն[խմբագրել | խմբագրել կոդը]

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

Բարդության ապացույց[խմբագրել | խմբագրել կոդը]

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

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

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

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

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

Մեքենայական կոդ[խմբագրել | խմբագրել կոդը]

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

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

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

for i := 2, 3, 4, ..., while i2n:
 if A[i] = true:
for j := i2, i2 + i, i2 + 2i, ..., while jn:
 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

Ծանոթագրություններ[խմբագրել | խմբագրել կոդը]

  1. Никомах Герасский, Введение в арифметику, I, 13. [1]
  2. Волшебное решето Эратосфена
  3. Hardy and Wright "An Introduction to the Theory of Numbers, p. 349
  4. Sedgewick Robert (1992)։ Algorithms in C++։ Addison-Wesley։ ISBN 0-201-51059-6  , p. 16.
  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).

Գրականություն[խմբագրել | խմբագրել կոդը]

Արտաքին հղումներ[խմբագրել | խմբագրել կոդը]