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

Հնարավոր է շատ արագ գտնել n-ից փոքր բոլոր պարզ թվերը։ Պետք չէ հերթով բոլոր թվերի (սկսած 2-ից մինչև n) համար ստուգել արդյոք այն պարզ է թե ոչ: Փոխարենը, կարող ենք մոտեցումը փոխել այնպես, որ ոչ թե յուրաքանչյուր թիվ առանձին ստուգենք, այլ ջնջենք այն թվերը, որոնք վստահ ենք, որ պարզ չեն:

Սկզբում պատկերացնենք, որ 2-ից մինչև n թվերը «հնարավոր է պարզ» պիտակով են. ապա ջնջում ենք 2-ի բոլոր բազմապատիկները և 2-ը հաստատում ենք որպես «պարզ»: Դրանից հետո ջնջում ենք 3-ի բոլոր բազմապատիկները և 3-ը ևս հաստատում ենք որպես «պարզ»: 4-ը բաց ենք թողնում, քանի որ այն արդեն ջնջվել է, երբ հեռացնում էինք 2-ի բազմապատիկները: Հաջորդ քայլին վերցնում ենք 5-ը և ջնջում 5-ի բոլոր բազմապատիկները: 6-ը բաց ենք թողնում, քանի որ այն նշվել է որպես ոչ պարզ դեռ 2-ը մշակելիս: Այսպես շարունակում ենք, մինչև հասնենք n-ին:

Էրատոսթենեսի մաղի պարզ սիմուլյացիա: Սեղմեք թվերի վրա և փորձեք թողնել միայն պարզ թվերը «միացված» վիճակներում, իսկ մնացածը «անջատված» սարքել:

Ալգորիթմի հետաքրքիր հատկություններ և օպտիմիզացիաներ

Հերթական p պարզ թվի բոլոր բազմապատիկները հերթով ջնջելու ամենակարևոր հատկություններից մեկն այն է, որ p-ի փոքր բազմապատիկները՝ 2·p, 3·p, 4·p, 5·p … արդեն ջնջվել են նախորդ քայլերում. հետևաբար, պետք չէ սկսել փոքր բազմապատիկներից և կարելի է անմիջապես սկսել p·p-ից:

Օրինակ, երբ 3-ն ենք մշակում, կարող ենք միանգամից սկսել 9-ից, քանի որ 6-ը արդեն ջնջվել է 2-ը մշակելիս: Նույն կերպ, երբ 5-ն ենք մշակում, սկսում ենք 25-ից, որովհետև 10-ը (2·5), 15-ը (3·5) և 20-ը (4·5) ջնջվել են նախորդ փուլերում:

prime = [True] * n                    # prime[i] = True => i-ը համարվում է պարզ
prime[0] = prime[1] = False           # 0 և 1 թվերը պարզ չեն

for i in range(2, n):                 # ցիկլ 2-ից մինչև n
    if prime[i]:                      # եթե i-ն պարզ է => նշել i-ի բազմապատիկները որպես ոչ պարզ
        for j in range(i * i, n, i):  # սկսում ենք i * i-ից, քանզի i-ից փոքր բազմապատիկները արդեն նշված են նախորդ քայլերի ընթացքում
            prime[j] = False

Էրատոսթենեսի մաղը պարզ n-ի փոքր բոլոր պարզ թվերը գտնելու համար։

Եկեք սիմուլյացիա կատարենք n=100-ի համար:

prime = [False, False, True, True, ..., True] չափսը 100

i = 2 ⇒ prime[2] = True ⇒ for j in 4, 6, 8, ... 100 և նշել prime[j]=False

i = 3 ⇒ prime[3] = True ⇒ for j in 9, 12, ... 100 և նշել prime[j]=False

i = 4 ⇒ prime[4] = False

i = 5 ⇒ prime[5] = True ⇒ for j in 25, 30, ... 100 և նշել prime[j]=False

i = 6 ⇒ prime[6] = False

i = 7 ⇒ prime[7] = True ⇒ for j in 49, 56, ... 100 և նշել prime[j]=False

i = 8 ⇒ prime[8] = False

i = 9 ⇒ prime[9] = False

i = 10 ⇒ prime[10] = False

i = 11 ⇒ prime[11] = True ⇒ for j in [դատարկ] և նշել prime[j]=False

Այստեղ կարող ենք դադարեցնել, քանի որ i * i-ն արդեն գերազանցում է n-ը: Ուստի այս պահից սկսած ոչ մի նոր թիվ չենք նշի որպես ոչ պարզ: Կարելի է պարզապես անցնել ամբողջ ցանկով և տպել 100-ից փոքր բոլոր պարզ թվերը:

Այս մոտեցումը զգալիորեն ավելի արագ է և կատարում է գործողություն: Սա մեծ տարբերություն կարող է տալ մեծ n-երի դեպքում: Եթե ալգորիթմը n քայլ անելով 10 տարի (3650 օր) էր աշխատելու, իսկ քայլ անելով՝ մոտ 2 ամիս (61 օր), ապա քայլերով այն կտևի ընդամենը 4 օրից էլ պակաս:

Ալգորիթմի ևս մեկ արագացում, որի մասին խոսվեց այս սիմուլյացիայի մեջ, հետևյալն է. կարելի է անցնել i-ի արժեքներով 2-ից մինչև , քանի որ ներսի ցիկլը սկսվում է i·i արժեքից, իսկ երբ i-ն գերազանցում է n-ի քառակուսի արմատը, ներսի ցիկլում այլևս ոչ մի թիվ չենք նշի որպես ոչ պարզ:

Մուտք

Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ n (2 ≤ n ≤ ):

Ելք

Ծրագիրը պետք է տպի n-ից փոքր կամ հավասար բոլոր պարզ թվերը։

Օրինակներ

Input	Output
8	2 3 5 7
17	2 3 5 7 11 13 17
19	2 3 5 7 11 13 17 19

Ալգորիթմի հետաքրքիր հատկություններ և օպտիմիզացիաներ

Մուտք

Ելք

Օրինակներ

Constraints

To check your solution you need to sign in

Sign in to continue