36 Agar kengaytma tub sonlarni o'z ichiga olsa, bu usulni qo'llash qiyin .
Masalan, GCD (1558, 1394) = 41, 1558=2 19 41, 1394=2 17 41
2.2.3.GCD ni topish uchun Evklid algoritmi
a) Ayirish orqali.
13
1260
|
432
|
828
|
432
|
396
|
432
|
396
|
36
|
369
|
36
|
324
|
36
|
288
|
36
|
252
|
36
|
216
|
36
|
180
|
36
|
144
|
36
|
108
|
36
|
72
|
36
|
36
|
36
|
1 2 3 4 5 6 7 8 9 10 11 12 13 gcd(1260; 432)= 36
Hisoblash uchun 13 qadam kerak.
Xulosa. Qo'llash oson, lekin juda uzoq davom etishi mumkin.
b) bo'linish.
Dastlabki ma’lumotlar: 1260 va 432 1260=432 2+396396 va 432 432=396 1+36
396 va 36 36= 36 11+0
Demak, GCD(1260; 432)= 36 Hisoblash uchun 3 qadam kerak.
Xulosa. Qo'llash oson.
2.1.4. Ikkilik Evklid algoritmi
gcd(1260; 432)= 2gcd(630, 216) = 2 2gcd(315, 108)=4gcd(315, 54)= 4gcd(315, 27) = 4 9=36,
chunki GCD(315, 27) = 3 3=9 (315=3 3 5 7; 27=3 3 3) Hisoblash uchun sizga 9 bosqich va GCD xulosasini topishning boshqa usullarini bilish kerak
Do'stlaringiz bilan baham: |
