Թվի պարզ լինելը ստուգելու արագ եղանակը
Մինչ այժմ, ստուգում էինք, թե արդյոք տրված
n թիվը պարզ է, թե ոչ, հիմնականում գծային որոնման (linear search) եղանակով: Դա նշանակում է, որ եթե n-ը մեծացնենք, ապա դրա պարզությունը ստուգելու համար անհրաժեշտ գործողությունների քանակը նույնպես համեմատական կերպ կավելանա (որոշ հաստատունի բազմապատիկով): Հաշվի առնելով ամենավատ դեպքերը (երբ n-ը հենց պարզ թիվ է, օրինակ՝ 51, 107 և այլն)՝ մեր ալգորիթմը մոտավորապես կատարում էր n/4 գործողություն, որպեսզի ստուգի n-ի պարզ լինելը:Փաստորեն, եթե
n-ը 10 անգամ մեծացնենք, ալգորիթմը կկատարի 10 անգամ ավելի շատ գործողություն: Եթե n-ը 100 անգամ մեծացնենք, ալգորիթմը կկատարի 100 անգամ ավելի շատ գործողություն: Ուրեմն մեր ալգորիթմի աշխատանքը համեմատական է n-ին: Իսկ կարելի՞ է այդ ստուգումը կատարել ավելի արագ: Թվում է, թե մենք դեռ շատ ավելորդ գործողություններ ենք կատարում: գործողությամբ ստուգելու մոտեցում.
Ենթադրենք
n թիվի բաժանարարներից մեկը d-ն է:Սա նշանակում է, որ
n-ը բաժանվում է d-ի, և թե՛ d-ն, թե՛ -ն ամբողջ թվեր են: Ավելին, կարող ենք պնդել, որ կամ d-ն, կամ -ն փոքր կամ հավասար են -ից: Հետևաբար, երբ ստուգում ենք, թե արդյոք թիվը պարզ է, կարող ենք թվերը ցիկլով ստուգել մինչև , ոչ թե մինչև : Մեզ հետաքրքրում է միայն, թե թիվն ունի՞ բաժանարար՝ 1-ից և n-ից տարբեր։ Քանի որ այդ բաժանարարներից ամենափոքրը կլինի ավելի փոքր կամ հավասար -ից, ուրեմն բավարար է ստուգել մինչև ու դադարեցնել գործողություններն այդտեղ:Սա մեծ առաջընթաց է:
n գործողությունների փոխարեն գործողություն կատարելը էական տարբերություն է տալիս: Պատկերացրեք ալգորիթմ, որը պետք է աշխատեր 10 տարի (3650 օր) ինչ-որ հաշվարկ կատարելու համար. եթե այն փոխարինեք n-ի փոխարեն գործողություն անող ալգորիթմով, ապա նույն խնդիրը կլուծվեր մոտ 2 ամսում (61 օր):Իսկ գոյություն ունե՞ն ավելի արդյունավետ ալգորիթմներ թվերի պարզությունը ստուգելու համար:
Այո՛։ Դրանց մասին կարող եք կարդալ Algorithms for Competitive Programming կայքում։ Կան ալգորիթմներ, որոնց գործողությունների քանակը կախված
n-ից աճում է լոգարիթմական կերպով, այլ ոչ թե -ի կարգով:Մուտք
Մուտքի առաջին տողում տրված է
n ամբողջ թիվը (1 ≤ n ≤ ):Ելք
Ծրագիրը ելքում պետք է տպի
Yes, եթե n-ը պարզ է, և No հակառակ դեպքում:Օրինակներ
Input | Output |
1 | No |
11 | Yes |
353557 | Yes |
34134741 | No |
902468477 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB