Chương trình tìm GCD/HCF của hai số trong C++

Tìm Ước Chung Lớn Nhất (GCD/HCF) của hai số bằng thuật toán Euclid đệ quy.

Thuật toán

• Nếu a==0 → b; b==0 → a.
• Nếu a==b → a.
• Nếu a>b → GCD(a-b,b); ngược lại GCD(a,b-a).

Ví dụ triển khai (C++)

#include <iostream>
using namespace std;

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

int main() {
    int a = 98, b = 56;
    cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
    return 0;
}

Đầu ra

GCD of 98 and 56 is 14