Tìm ước chung lớn nhất (GCD) của hai số

Giới thiệu

Trong toán học, Ước chung lớn nhất (GCD - Greatest Common Divisor) là số nguyên lớn nhất có thể chia hết cả hai số nguyên. Điều kiện là các số phải khác không.

Chúng ta sẽ sử dụng thuật toán Euclid để tìm GCD của hai số.

Đầu vào và Đầu ra

Đầu vào: Hai số 51 và 34
Đầu ra: GCD là: 17

Thuật toán

findGCD(a, b)
Đầu vào: Hai số a và b.
Đầu ra: GCD của a và b.

Begin
    if a = 0 OR b = 0, then
        return 0
    if a = b, then
        return b
    if a > b, then
        return findGCD(a-b, b)
    else
        return findGCD(a, b-a)
End

Ví dụ (C++)

#include <iostream>
using namespace std;

int findGCD(int a, int b) {
    // giả sử a lớn hơn b
    if(a == 0 || b == 0)
        return 0;  // vì a và b là 0, ước chung lớn nhất cũng là 0
    if(a == b)
        return b;  // khi cả hai số giống nhau
    if(a > b)
        return findGCD(a-b, b);
    else
        return findGCD(a, b-a);
}

int main() {
    int a, b;
    cout << "Enter Two numbers to find GCD: "; cin >> a >> b;
    cout << "The GCD is: " << findGCD(a,b);
}

Kết quả

Enter Two numbers to find GCD: 51 34
The GCD is: 17