Արդյո՞ք թիվը պարզ է (Prime Numbers)
Tags: algorithms, javascript
Published: 2021-12-03 10:26:34

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

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

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

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

---

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

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

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

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

![code javascript](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ksfmlenmfqqa6a09o64v.png)

[Կոդը տեղադրված է այս հղման մեջ](https://codepen.io/b11rdman/pen/NWaqJJO?editors=0011)

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

![code javascript](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/01786l7pvlxxk6rwe7yh.png)

[Կոդը տեղադրված է այս հղման մեջ](https://codepen.io/b11rdman/pen/rNGVREa?editors=0011)

---

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

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

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

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

1. `A > M => B < M`
2. `A = M => B = M`
3. `A < M => B > M`

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

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

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

![code javascript](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8i7urze2qy7977rf0rjl.png)

[Կոդը տեղադրված է այս հղման մեջ](https://codepen.io/b11rdman/pen/dyVoLPR?editors=0011)

Հույս ունեմ, այս նյութը քեզ օգնեց նոր գաղափարներ և նոր գիտելիք ստանալու հարցում։ Իսկ եթե ունես այնպիսի լուծման եղանակ, որը այստեղ նշված չէ, շատ ուրախ կլինեմ, [եթե քո տարբերակը ուղարկես ինձ](https://t.me/Beardman1104), այդպիսով փորձի փոխանակում կանենք։