Արդյո՞ք թիվը պարզ է (Prime Numbers)

#algorithms #javascript

Բարև սիրելի ծրագրավորող (կամ ապագա ծրագրավորող)։

Այսօր կնայենք հարցազրույցների ժամանակ ամենատարածված խնդիրներից մեկը՝ թվի պարզությունը ստւգելու խնդիրը և այդ խնդրի լուծման եղանակներից մի քանիսը։

Սակայն մինչև առաջ անցնելը 2 կարևոր բան
֊ Խնդիրների լուծումները կլինեն JavaScript լեզվով,
֊ Ես ներկայացնում եմ խնդիրը լուծելու գաղափարները և չեմ բացատրելու, թե որ ֆունկցիան իրենից ինչ է ներկայացնում, սակայն կտեղադրեմ համապատասխան հղումները, որպեսզի դու ինքդ ուսումնասիրես դրանք:

Եթե սիրում ես խնդիրներ լուծել, ուրեմն արդեն լուծել ես այսպիսի խնդիր։ Կամ հարցազրույցի ժամանակ առընչվել ես այսպիսի խնդրի։

Նախ հասկանանք խնդիրը։
Ո՞ր թվերն են համարվում պարզ թվեր։
Պարզ թիվ է կոչվում այն բնական թիվը (բացի 1-ից), որը ունի միայն երկու բաժանարար։ Այսինքն բաժանվում են միայն մեկի և իր վրա ։

Ի՞նչպես կարող ենք ստուգել թվի պարզ լինելը։
Ենթադրենք մեզ տրված թիվը N թիվն է։
Պարզապես կարող ենք մինչև N բոլոր թվերը հերթով ստուգել և եթե գտնենք 1֊ից և N֊ից տարբեր այնպիսի թիվ, որի վրա N֊ը բաժանելիս ստանում ենք 0 մնացորդ, ուրեմն թիվը պարզ չէ։

Ընդունենք, որ մեր ֆունկցիային փոխանցվող արգումենտը միշտ 1֊ից տարբեր բնական թիվ է լինելու {2,3,4,5,...}:

Մեզ պետք է գտնենլ 1֊ից և N֊ից տարբեր թիվ, հետևաբար կարող ենք ստուգել [2, N-1] միջակայքի թվերը, ներառյալ։

Կոդը տեղադրված է այս հղման մեջ

Այս եղանակի վրա կարող ենք որոշակի օպտիմիզացիաներ կատարել։
Օրինակ կարող ենք ստուգել մինչև N/2, որովհետև (N/2, n] միջակայքում այնպիսի թիվ չկա, որի վրա բաժանելիս կստանանք` ամբողջ թիվ (կստանանք 1ից մեծ և 2ից փոքր թվեր)։ Այսպիով մեր քալերի քանակը 2 անգամ կկրճատվի։

Կոդը տեղադրված է այս հղման մեջ

Սակայն կա մեկ այլ, ավելի օպտիմալ տարբերակ, որը սկզբից կբացատրեմ մաթեմատիկական եղանակով։

Ցանկացած բնական, ոչ պարզ N թիվ կարող ենք ներկայացնել A * B տեսքով, որտեղ A, B֊ն նույնպես բնական թվեր են։
Ունենք M դրական իրական թիվը, որը N թվի քառակուսի դրական արմատն է՝ M = |√ N|:

Քանի որ M * M = N և N = A * B, ապա M * M = A * B

Նկատենք, որ ստորև նշված 3 պայմաններից մեկը միշտ տեղի ունի։

A > M => B < M
A = M => B = M
A < M => B > M

Բոլոր 3 դեպքերի համար 1 ընդհանուր բան կա՝ (A,B)-ից փոքրագույնի արժեքը փոքր կամ հավասար է M֊ից (min(A,B) ≤ M):
Հետևաբար նրանցից մեծագույնը մեծ կամ հավասար է M֊ից (max(A,B) ≤ M):

Այսինքն, եթե N թիվը պարզ չէ, ուրեմն [2,M] միջակայքում գոյություն ունի գոնե 1 այնպիսի թիվ, որի վրա N֊ը առանց մնացորդ բաժանվում է։ Հակառակ դեպքում թիվը պարզ է։

Այս ալգորիթմը էլ ավելի քիչ քայլում է կատարվում, քայլերի քանակը հասցնելով √N֊ի։

Կոդը տեղադրված է այս հղման մեջ

Հույս ունեմ, այս նյութը քեզ օգնեց նոր գաղափարներ և նոր գիտելիք ստանալու հարցում։ Իսկ եթե ունես այնպիսի լուծման եղանակ, որը այստեղ նշված չէ, շատ ուրախ կլինեմ, եթե քո տարբերակը ուղարկես ինձ, այդպիսով փորձի փոխանակում կանենք։