Jump to content

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

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Էրատոսթենեսի մաղ
Տեսակ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 in:
 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. Վերցված է 2011 թ․ հոկտեմբերի 26-ին., 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).

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

[խմբագրել | խմբագրել կոդը]

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

[խմբագրել | խմբագրել կոդը]