If you're seeing this message, it means we're having trouble loading external resources on our website.

Եթե գտնվում ես վեբ զտիչի հետևում, խնդրում ենք համոզվել, որ *.kastatic.org և *.kasandbox.org տիրույթները հանված են արգելափակումից։

Հիմնական նյութ

Փորձնական բաժանում

Սահմանենք խնդիրը

Պետք է ստեղծենք մեքենա, որը կարող է պատասխանել պարզ այո/ոչ հարցին։ Պա՞րզ է ներմուծված n թիվը, թե՞ ոչ։
Արի մտածենք, թե ինչ պետք է կատարվի մեքենայի մեջ, որ այն աշխատի։ Մեքենաները միայն կարող են կատարել քայլերի հերթականություն՝ տրված ուղղորդումներով, որը մեր լեզվով հայտնի է որպես ալգորիթմ։ Տաքանալու համար արի հասկանանք, թե ինչ ալգորիթմ է աշխատում քո ուղեղի ներսում։ Պատասխանիր այս հարցին․ 49-ը պա՞րզ թիվ է։
Չէ՞։ Ինչպե՞ս ստացար դա։ Դու 49-ին հավանաբար բաժանարար էիր փնտրում, որը մեծ է 1-ից և փոքր է 49-ից։ Եթե չես մտապահել բազմապատկման աղյուսակը, ապա դու այսպիսի մի հերթականությամբ գտած կլինեիր․
  • 49-ը բաժանվո՞ւմ է 2-ի վրա։     ՈՉ
  • 49-ը բաժանվո՞ւմ է 3-ի վրա։     ՈՉ
  • 49-ը բաժանվո՞ւմ է 4-ի վրա։     ՈՉ
  • 49-ը բաժանվո՞ւմ է 5-ի վրա։     ՈՉ
  • 49-ը բաժանվո՞ւմ է 6-ի վրա։     ՈՉ
  • 49-ը բաժանվո՞ւմ է 7-ի վրա։   ԱՅՈ
Մենք գտանք թիվ, որի վրա բաժանվում էր 49-ը (7), ինչը ցույց է տալիս, որ 49-ը բաղադրյալ թիվ է։

Կառուցենք պատը

Իսկ ի՞նչ կլիներ, եթե հարցնեի՝ 2971215073-ը պարզ թիվ է, թե ոչ։
Դու դեռ ստուգո՞ւմ ես։ Առաջին հազար թեստից հետո ես դեռ չեմ գտել բաժանարար։ Կարևոր հարցը սա է․ ե՞րբ ենք կանգնում և ասում, որ n-ը պարզ է (արի սա կոչենք մեր պատը)։ Որպես սկսվող կետ՝ մենք գիտենք, որ մեր պատը պետք է լինի n-1 (քանի որ n-ը բաժանվում է n-ի վրա)։ Եթե մինչև 2971215072-ը ստուգենք, կամ կգտնենք բաժանարար (որից հետևում է, որ n-ը բաղադրյալ է), ԿԱՄ չենք գտնի (որից հետևում է, որ n-ը պարզ է

Ավելի լավ պատ կառուցենք

Սա կաշխատի, բայց կարո՞ղ ենք տեղաշարժել պատը, որ ժամանակ շահենք։ Հիշիր, որ մենք փնտրում ենք միայն առաջին (կամ ամենափոքր) բաժանարարը։ Երբեմն այն կարող է լինել 2, երբեմն էլ այն շատ մեծ թիվ է։ Սրանից բխում է մի շատ կարևոր հարց․ որքա՞ն մեծ կարող է լինել թվի ամենափոքր բաժանարարը։
Հիշիր, որ յուրաքանչյուր բաղադրյալ ամբողջ թիվ կառուցված է երկու կամ ավելի պարզ թվերի արտադրյալով՝ n= P * P …
P-ն ամենամեծ արժեքն ունի, երբ n-ն ունի երկու պարզ բաժանարար, որոնք հավասար են իրար։ Սա մեզ հայտնի է, որպես լրիվ քառակուսի, ինչպիսին է,, օրինակ՝ 9 (9 = 33) կամ 49 (49 = 77)։Այն վատագույն դեպքի հետ համընկնելու համար մենք մեր պատը շարում ենք n-ի քառակուսի արմատի դիրքում։
Համոզվիր սրանում: Եթե չենք գտնում n-ի բաժանարար՝ հասնելով մինչև n-ի քառակուսի արմատը, ապա n-ը պարզ թիվ է։ Սա փորձիր ինքնուրույն ապացուցել (ապացույցն այս հոդվածի ներքևում է)։

Փորձնական բաժանման ալգորիթմ

Վերջ, մենք պատրաստ ենք անցնել առաջ։ Սկզբում արի փորձնական բաժանման ալգորիթմը ներկայացնենք անմարդկային հայերենով․
  • Մուտքագրենք ինչ-որ ամբողջ թիվ: n
  • Յուրաքանչյուր x-ի համար, որը պատկանում է {2 ... sqrt(n)} միջակայքին, ստուգիր՝ n-ը բաժանվում է արդյոք x-ի վրա, թե ոչ:
  • Եթե գտել ես բաժանարար, ապա n-ը բաղադրյալ է, այլապես n-ը պարզ թիվ է
Եթե ունես ծրագրավորման գիտելիքներ, պետք է բացես դատարկ պատուհան և փորձես գրել ու աշխատեցնել այս ֆունկցիան։ Եթե ոչ, կարող ես անցնել հաջորդ քայլին, որտեղ ցույց կտամ աշխատող տարբերակ, որը քեզ համար լավ սկզբնակետ կլինի։ (Եթե ուզում ես, կարող ես այս դասն անցնել առանց ծրագրավորում անելու)։

Ուզո՞ւմ ես միանալ խոսակցությանը։

Առայժմ հրապարակումներ չկան։
Անգլերեն հասկանո՞ւմ ես: Սեղմիր այստեղ և ավելի շատ քննարկումներ կգտնես «Քան» ակադեմիայի անգլերեն կայքում: