Էրատոսթենեսի մաղ մինչև n որոշակի ամբողջ թիվը եղած պարզ թվերը գտնելու ալգորիթմ, որի հայտագործումը վերագրում են հին հույն մաթեմատիկոս Էրատոսթենես Կիրենացուն։ Ինչպես և մնացած բոլոր դեպքերում, այստեղ ալգորիթմի անունը խոսում է նրա կատարած աշխատանքի սկզբունքի մասին, այսինքն մաղը իրենից ենթադրում է «զտում», այս դեպքում, բացի պարզ թվերից, «զտվում են» մնացած բոլոր թվերը։ Թվերի ցանկով առաջ անցնելիս պարզ թվերը մնում են, իսկ մնացած թվերը, որոնք կոչվում են բաղադրյալ թվեր, հեռացվում են։
Էրատոսթենեսի մաղ | |
---|---|
Տեսակ | primality test? |
Անվանված է | Էրատոսթենես Կիրենացի |
Համաձայն լեգենդի, մեթոդը ստացել է «մաղ» անվանումը, քանի որ Էրատոսթենեսը թվերը գրում էր մոմով պատված փոքրիկ տախտակի վրա, և անցք էր բացում այն տեղերում, որտեղ գրված էին բաղադրյալ թվեր։ Տախտակը նմանեցնում էին մաղի, որի միջոցով մաղում էին բաղադրյալ թվերը և թողնում միայն պարզ թվերը։ Էրատոսթենեսը կազմել է մինչև 1000 եղած պարզ թվերի ցանկը։
Մինչև տրված n թիվը եղած պարզ թվերը գտնելու համար, համաձայն Էրատոսթենեսի մեթոդի, անհրաժեշտ է կատարել հետևյալ քայլերը՝
Հիմա 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
Գրենք 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 3456789101112131415161718192021222324252627282930
Մյուս չջնջված թիվը՝3ը պարզ է։ Անցնելով ցանկով, ջնջենք 3ին պատիկ բոլոր թվերը(այսինքն ամեն երկրորդը, սկսած 32 = 9-ից )
2 3456789101112131415161718192021222324252627282930
Մյուս չջնջված թիվը՝5ը պարզ է։ Անցնելով ցանկով, ջնջենք 5ին պատիկ բոլոր թվերը(այսինքն ամեն երկրորդը, սկսած 52 = 25-ից ) և այսպես շարունակ՝
2 3456789101112131415161718192021222324252627282930
Մյուս չջնջված թիվը՝ 7, նրա քառակուսին՝ 49 ավելի մեծ է քան 30-ը, այսինքն աշխատանքը ավարտված է և պարզ թվերի ցանկը հետևյալն է՝
2 3 5 7 11 13 17 19 23 29
This article uses material from the Wikipedia Հայերեն article Էրատոսթենեսի մաղ, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Բովանդակությունը թողարկված է CC BY-SA 4.0 թույլատրագրով, եթե այլ բան նշված չէ։ Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Հայերեն (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.