Gcd va nocni topish va qo'llash

LCM(a, b)= (ab ) / GCD (a,b) ko'rinishiga ega [4] Yuqoridagi
formuladan foydalanib LCMni topish misollarini ko'rib chiqaylik .
Yechish Bu misolda a=126 , b=70 . LCM(a, b)= (ab)/ GCD (a,b)
formulasi bilan ifodalangan LCM ning GCD bilan bog‘lanishidan foydalanamiz , ya’ni,
avval 70 va 126 sonlarining eng katta umumiy bo‘luvchisini topishimiz kerak. bu sonlarning LKM ni
yozma formula bo‘yicha hisoblashimiz mumkin.Evklid algoritmidan
foydalanib
GCD(126, 70) ni toping : 126=70 1+56 , 70=56 1+14 , 56=14 4 , demak GCD(126, 70)=14 .
Endi biz kerakli eng kichik umumiy karrani topamiz: LCM(126,
70)=126 70:GCD(126, 70)=126 70:14=630 .
Javob: LCM(126, 70)=630 . 2-misol.
LCM(68, 34) nima ?
Yechish: 68 34 ga teng bo‘linadigan bo‘lgani uchun gcd(68, 34)=34 bo‘ladi . Endi
biz eng kichik umumiy karralini hisoblaymiz: LCM(68, 34)=68 34:GCD(68,
34)=68 34:34=68 .
Javob: LCM(68, 34)=68 .
12 E'tibor bering, oldingi misol
a va b musbat butun sonlar uchun LCMni topish uchun quyidagi qoidaga mos keladi
: agar a soni
b ga bo'linadigan bo'lsa, u holda bu sonlarning eng kichik umumiy karrali a bo'ladi.
2-bob Algoritmlarni qo'llash samaradorligini baholash
2.1. GCD hisoblash algoritmlarini solishtirish
GCD hisoblashni ko'rib chiqing (1260, 432)
2.1.1.Izlash.
1260 sonining boʻluvchilari:
2,3,4,5,6,7,9,10,12,14,15,18,20,21,28,30,35,36,42,45,60,63,70, 84,90,105,126,140,18
0,210,252,315,420,630 (34 qadam
) : 2,3,4,9,12,18,36. Demak, gcd(1260, 432)=36. Hisoblash uchun kamida 34 qadam kerak.
Xulosa: Hisoblashning ancha mashaqqatli usuli.
2.2.2. Asosiy omillarga parchalanish.
1260 2 432 2
630 2 216 2315 3 108 2105 3 54 235 5 27 37 7 9 31 3 31gcd(1260; 432)= 2 2 3 3=