Ստուգել, արդյոք թիվը պարզ է - մի փոքր ավելի արագ
Պատկերացրեք, որ մի մեծ ընկերություն արդեն օգտագործում է մի ծրագիր, որը ստուգում է թիվը պարզ է, թե՞ ո՛չ։ Քանի որ ընկերությունը բավականին արագ է զարգանում, օգտատերերի քանակը շատ արագ աճում է, և ձեր ծրագիրը ստանում է ավելի ու ավելի շատ հարցումներ։ Նրանք խնդրում են ձեզ օպտիմիզացնել կոդը, որպեսզի ծրագիրն ավելի արագ կատարի ստուգումները և կարողանա սպասարկել նոր օգտատերերի մեծ հոսքը:
Նախորդ ծրագրի տեսքը հետևյալն էր.
- Ցիկլով ստուգել բոլոր թվերը 2-ից մինչև
nև հաշվել բաժանարարների քանակը։
- Ցիկլով ստուգել բոլոր թվերը 2-ից մինչև
nև կանգ առնելու հենց գտնում ենք ինչ-որ բաժանարար։
Կան մի քանի փոքր հնարքներ, որոնք կարող ենք իրականացնել գործընթացը բարելավելու համար.
Առաջին օպտիմիզացիա.
2-ից մինչև
n բոլոր թվերը ստուգելու փոխարել, կարելի է նախ ստուգել, թե արդյոք n-ը բաժանվում է 2-ի վրա։ Եթե ոչ, ապա այլ զույգ թվեր (4, 6, 8, 10 և այլն) ստուգելու կարիք չի լինելու, քանի որ եթե 2-ի վրա չի բաժանվում, մյուս զույգ թվերի վրա նույնպես չէր կարող բաժանվել:Երկրորդ օպտիմիզացիա.
2-ից մինչև
n ամբողջ միջակայքը ստուգելու փոխարեն, կարող ենք ստուգել մինչև n/2, որովհետև եթե ամենափոքր բաժանարարը 2-ն է, ապա n/2-ից մեծ բաժանարար չի կարող լինել:Այս երկու օպտիմիզացումները կարելի է համատեղել։ Այս դեպքում ստուգվելու ենք միայն մինչև
n/2 թվերը, և դրանցից էլ միայն կենտ թվերը։ Կստացվի մոտավոր n/4 թեկնածու բաժանարար, ու ծրագիրը զգալիորեն ավելի արագ կաշխատի:Այս օպտիմիզացիաների արդյունքում ծրագիրը մի փոքր ավելի կշտապի, սակայն բարդության առումով այն դեռ շարունակում է գծային ստուգում կատարել, այսինքն՝
n-ի մեծացմանը զուգընթաց, քայլերի քանակը շարունակում է աճել n-ին ուղիղ համեմատական։ Ապագայում կխոսենք այն մասին, թե ինչպես կարելի է արագացնել պարզ թվերի ստուգումը, որպեսզի այն ուղիղ համեմատական չլինի n-ի աճին։Մուտք
Մուտքի առաջին տողում տրված է
n ամբողջ թիվը (1 ≤ n ≤ )։Ելք
Ծրագիրը պետք է տպի
Yes, եթե n-ը պարզ է, հակառակ դեպքում պետք է տպի No:Օրինակներ
Մուտք | Ելք |
8 | No |
7 | Yes |
1 | No |
19 | Yes |
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB