Thuật toán tìm Ước chung lớn nhất của hai số

Với việc tìm Ước chung lớn nhất của 2 số, chúng ta có nhiều thuật toán. Dưới đây là một ví dụ về tìm ước chung lớn nhất sử dụng đệ quy:

#include <iostream>
using namespace std;

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main()
{
    int a, b;
    cout << "Nhap a va b: ";
    cin >> a >> b;
    cout << "Uoc chung lon nhat cua " << a << " va " << b << " la: " << gcd(a, b);
    return 0;
}

Ở đây, gcd là hàm đệ quy để tính GCD của hai số a và b. Nếu b bằng 0, a chính là GCD của hai số. Nếu không, ta chuyển sang tính GCD của b và phần dư của a chia cho b.

Trong hàm main, ta nhập hai số a và b từ người dùng, sau đó gọi hàm gcd để tính và xuất kết quả GCD.

Thuật toán Euclid là thuật toán tìm ước chung lớn nhất nhanh nhất. Thuật toán này dựa trên tính chất sau đây của GCD:

Nếu a >= b và r là phần dư của a chia cho b, thì GCD(a, b) = GCD(b, r).

Có nghĩa là, để tìm GCD của a và b, ta thực hiện việc chia a cho b để tính phần dư r, sau đó dùng b và r để tính lại GCD. Tiến hành như vậy cho đến khi phần dư r bằng 0, khi đó GCD là b.

Dưới đây là mã C++ cho thuật toán Euclid:

#include <iostream>
using namespace std;

int gcd(int a, int b)
{
    while (b != 0)
    {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main()
{
    int a, b;
    cout << "Nhap a va b: ";
    cin >> a >> b;
    cout << "Uoc chung lon nhat cua " << a << " va " << b << " la: " << gcd(a, b);
    return 0;
}

Trong hàm gcd, ta sử dụng vòng lặp while để thực hiện việc chia a cho b để tính phần dư r, sau đó gán giá trị của b cho a và giá trị của r cho b. Khi b bằng 0, ta trả về giá trị của a là GCD của a và b.

Với cách tiếp cận này, thuật toán Euclid có độ phức tạp thời gian là O(log(min(a, b))), nhanh hơn so với cách tiếp cận đệ quy trong trường hợp a và b lớn.