Chương trình tìm ước chung lớn nhất (UCLN) của hai số

Giả sử có hai số a và b, nhiệm vụ của chúng ta là tìm ước chung lớn nhất của hai số này.

Chú ý: UCLN (Ước chung lớn nhất) của hai số là số lớn nhất mà chia cả hai số đó.

Ví dụ:

Input: a = 20, b = 28 Output: 4 Giải thích: Các ước của số 20 là 1, 2, 4, 5, 10 và 20. Các ước của số 28 là 1, 2, 4, 7, 14 và 28. Trong số các ước này, 1, 2 và 4 là các ước chung của cả 20 và 28. Ước chung lớn nhất trong các ước chung này là 4.

Input: a = 60, b = 36 Output: 12

Phương pháp thông thường để tìm UCLN của hai số:

Ý tưởng cơ bản là tìm số nhỏ nhất trong hai số và tìm ước chung lớn nhất của nó, đồng thời ước chung này cũng là ước chung của số còn lại.

Dưới đây là cách thực hiện ý tưởng trên:

def gcd(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a

Thuật toán Euclid để tìm UCLN của hai số:

Ý tưởng của thuật toán này là UCLN của hai số không thay đổi nếu số nhỏ hơn được trừ đi từ số lớn hơn. Đây là thuật toán Euclid thông qua phép trừ. Quy trình này lặp lại việc trừ đi, đồng thời mang kết quả tiếp tục cho đến khi kết quả bằng bất kỳ số nào trong hai số đang được trừ đi.

Pseudo-code cho thuật toán này:

gcd(a, b):
    if a = b:
        return a
    if a > b:
        return gcd(a - b, b)
    else:
        return gcd(a, b - a)

Dưới đây là cài đặt của phương pháp trên:

def gcd(a, b):
    if a == b:
        return a
    if a > b:
        return gcd(a - b, b)
    else:
        return gcd(a, b - a)

Tối ưu hóa bằng cách kiểm tra tính chia hết:

Phương pháp trên có thể tối ưu dựa trên ý tưởng sau:

Nếu quan sát phương pháp trước đó, ta có thể thấy tại một số điểm, một số trở thành ước chung của số còn lại, vì vậy thay vì lặp đi lặp lại cho tới khi cả hai số trở thành bằng nhau, chúng ta có thể kiểm tra xem nó có phải là ước chung của số kia hay không.

Thêm ví dụ để hiểu rõ hơn:

Xem ví dụ dưới đây để hiểu rõ hơn:

Xét a = 98 và b = 56

a = 98, b = 56:

• a > b nên a = a - b và b không thay đổi. Vậy a = 98 - 56 = 42 và b = 56.

a = 42, b = 56:

• Vì b > a, chúng ta kiểm tra xem b%a = 0 không. Vì kết quả là không, chúng ta tiếp tục.
• Tiếp theo, b > a. Vậy b = b - a và a không thay đổi. Vậy b = 56 - 42 = 14 và a = 42.

a = 42, b = 14:

• Vì a > b, chúng ta kiểm tra xem a%b = 0 không. Bây giờ kết quả là có.
• Vậy chúng ta in ra số nhỏ hơn trong a và b là UCLN. Tức là 42 gấp 3 lần 14.

Vậy UCLN là 14.

Dưới đây là cài đặt của phương pháp trên:

def gcd(a, b):
    while b != 0:
        temp = b
        b = a % b
        a = temp
    return a

Tối ưu hóa bằng cách sử dụng phép chia:

Thay vì thuật toán Euclid bằng phép trừ, chúng ta có thể sử dụng phép chia liên tục. Điều này là một phương pháp tối ưu hơn. Dưới đây là cài đặt của phương pháp trên:

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

Cài đặt lặp để tìm UCLN của hai số bằng thuật toán Euclid:

Dưới đây là cách tìm UCLN của hai số bằng thuật toán Euclid bằng phương pháp lặp:

def gcd(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a

Tìm UCLN của hai số bằng hàm tích hợp sẵn:

Một số ngôn ngữ như C++ có các hàm tích hợp sẵn để tính UCLN của hai số.

Dưới đây là cài đặt sử dụng các hàm tích hợp sẵn:

import math

def gcd(a, b):
    return math.gcd(a, b)

Vui lòng tham khảo UCLN của nhiều hơn hai (hoặc mảng) số để tìm UCLN của nhiều hơn hai số.