Thuật toán tìm UCLN của hai số nguyên dương

UCLN (ước chung lớn nhất) của 2 số là gì?

Ước chung lớn nhất (UCLN, tiếng Anh là GCD – Greatest Common Divisor) của 2 số nguyên dương a và b là số nguyên lớn nhất d thỏa mãn tính chất cả a và b đều chia hết cho d.

Ví dụ, UCLN của 10 và 35 là 5 vì 5 là số nguyên lớn nhất mà cả 10 và 35 đều chia hết cho 5.

Thuật toán tìm UCLN của hai số nguyên dương

Có nhiều thuật toán tìm UCLN của hai số nguyên, bạn có thể tham khảo thêm ở Wikipedia. Dưới đây, chúng tôi giới thiệu thuật toán tìm UCLN của hai số nguyên giải thuật Euclid. Cơ sở của giải thuật Euclid tìm UCLN của hai số nguyên a và b dựa trên tính chất sau.

Giả sử a >= b thì khi chia a cho b ta được thương q và số dư r, tức là

a = b*q + r

Khi đó:

• Nếu r = 0 thì UCLN(a,b) = b
• Nếu r >0 thì UCLN(a,b) = UCLN(b,r)

Tìm UCLN của hai số nguyên bằng phép chia

Áp dụng giải thuật Euclid để tính ƯCLN của a = 1071 và b = 462. Đầu tiên, ta chia 1071 cho 462 thì được thương là 2 và số dư là 147:

1071 = 2 × 462 + 147.

Do đó, UCLN(1071,462) = UCLN(462, 147). Tiếp tục chia 462 cho 147 thì được thương bằng 3 và số dư là 21:

462 = 3 × 147 + 21.

Do đó, UCLN(462,147) = UCLN(147, 21). Tiếp tục chia 147 cho 21 thì được thương là 7 và số dư là 0:

147 = 7 × 21 + 0.

Do đó, UCLN(1071,462)=21.

Giả mã của thuật toán này như sau:

function gcd(a, b)
    while b ≠ 0
        t:= b
        b:= a mod b
        a:= t
    return a

Một cách ngắn gọn, để tìm UCLN của hai số x và y có thể xem trong hình sau:

Đối với chương trình viết bằng Dart, bạn có thể tham khảo code tại đây https://divin.dev/dart/2021/10/14/bai-tap-dart-15.html

Nếu sử dụng hàm, hoặc đệ quy, mời bạn tham khảo trong bài…

Tìm UCLN của hai số nguyên bằng phép trừ

Tìm UCLN của hai số nguyên bằng cách phép trừ. Ở đây, chúng ta sử dụng không sử dụng phép chia mà sử dụng tính chất sau nếu a và b cùng chia hết cho d thì hiệu a-b cũng chia hết cho d.

Ví dụ, xét hai số nguyên 15 và 9 thì UCLN(15,9) = UCLN(15-9,9).

Giả mã của thuật toán này như sau:

function gcd(a, b)
    while a ≠ b 
        if a > b
            a:= a − b
        else
            b:= b − a
    return a

Bạn có thể tham khảo mã nguồn tại đây https://divin.dev/dart/2021/10/14/bai-tap-dart-15.html

Xem thêm: Thuật toán quay lui và minh họa