Chương trình C++ tìm UCLN hai số bằng thuật toán Euclid đệ quy

Ước chung lớn nhất (GCD) của hai số là số lớn nhất chia hết cả hai.

Ví dụ: 63 = 7 × 3 × 3, 21 = 7 × 3 → UCLN(63, 21) = 21.

Thuật toán Euclid đệ quy: GCD(a, b) = GCD(b, a % b) cho đến khi b = 0.

Ví dụ

#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 << "Enter the values of a and b: " << endl;
    cin >> a >> b;
    cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
    return 0;
}

Kết quả

Enter the values of a and b: 105 30
GCD of 105 and 30 is 15

Hàm gcd() đệ quy

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

Hàm main()

int main() {
    int a, b;
    cout << "Enter the values of a and b: " << endl;
    cin >> a >> b;
    cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
    return 0;
}