Tìm UCLN của hai số không dùng đệ quy hay thuật toán Euclid trong C++

Như所周知, UCLN (HCF/GCD) có thể tính dễ dàng bằng thuật toán Euclid. Tuy nhiên, đây là cách tìm UCLN không sử dụng thuật toán Euclid hay đệ quy. Ví dụ: hai số 16 và 24, UCLN là 8.

Cách tiếp cận đơn giản: Nếu số lớn hơn chia hết cho số nhỏ hơn, thì số nhỏ đó chính là UCLN. Ngược lại, duyệt từ (số nhỏ / 2) xuống 1, nếu phần tử hiện tại chia hết cả hai số thì đó là UCLN.

Ví dụ minh họa

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    int min_num = min(a, b);
    if (a % min_num == 0 && b % min_num == 0)
        return min_num;
    for (int i = min_num / 2; i >= 2; i--) {
        if (a % i == 0 && b % i == 0)
            return i;
    }
    return 1;
}

int main() {
    int a = 16, b = 24;
    cout << "UCLN: " << gcd(a, b);
    return 0;
}

Kết quả

UCLN: 8