Chương trình tìm UCLN (Ước chung lớn nhất) của 2 số trong C++

Tìm Ước Chung Lớn Nhất (HCF/GCD) của hai số nguyên dương.

Thuật toán Euclid (đệ quy)

• Nếu a == b → trả về a.
• Nếu a > b → GCD(a-b, b).
• Ngược lại → GCD(a, b-a).
• Cơ sở: a==0 hoặc b==0 → 0.

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

#include <stdio.h>

int gcd(int a, int b) {
    if (a == 0 || b == 0) return 0;
    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;
    printf("GCD of %d and %d is %d ", a, b, gcd(a, b));
    return 0;
}

Đầu ra

GCD of 98 and 56 is 14