Thuật toán tìm ước chung lớn nhất

Giải thuật Euclid, hay Thuật toán Euclid, là một giải thuật giúp tính ước số chung lớn nhất (ƯSCLN) của hai số một cách hiệu quả. Giải thuật này đã được biết đến từ khoảng năm 300 trước Công Nguyên. Nhà toán học Hy Lạp cổ Euclid đã viết giải thuật này trong cuốn sách toán nổi tiếng Elements.

Ở dạng đơn giản nhất, thuật toán Euclid bắt đầu với cặp số nguyên dương, và tạo ra một cặp số nguyên dương mới bao gồm số nhỏ hơn và phần dư của phép chia hai số ban đầu. Quá trình được tiếp tục cho đến khi hai số trong cặp bằng nhau, giá trị lúc đó sẽ trở thành ước số chung lớn nhất của cặp số ban đầu.
Nguyên lý chính của thuật toán là ước số chung lớn nhất của một cặp số không thay đổi với hiệu của hai số đó. Ví dụ như ƯSCLN của 252 và 105 chính bằng ƯSCLN của 147 (= 252 − 105) và 105. Vì số lớn hơn trong cặp số bị giảm giá trị nên việc lặp đi lặp lại thuật toán này giúp tạo ra những số ngày càng nhỏ và đến một lúc nào đó quá trình này sẽ kết thúc — khi cặp số còn lại hai số bằng nhau (nếu quá trình được thực hiện thêm một bước nữa, sẽ có một trong hai số trở thành số 0).
Phương pháp 1:
Tìm UCLN sử dụng phép trừ
Đây là sơ đồ của thuật toán này

Code minh họa

int gcd(int a, int b){
    // Nếu a = 0 => ucln(a,b) = b
    // Nếu b = 0 => ucln(a,b) = a
    if (a == 0 || b == 0){
        return a + b;
    }
    while (a != b){
        if (a > b){
            a -= b; // a = a - b
        }else{
            b -= a;
        }
    }
    return a; // return a or b, bởi vì lúc này a và b bằng nhau
}

Phương pháp 2: Tìm UCLN sử dụng phép chia dư
Code minh họa

int gcd(int a, int b){
    // Lặp tới khi 1 trong 2 số bằng 0
    while (a*b != 0){
        if (a > b){
            a %= b; // a = a % b
        }else{
            b %= a;
        }
    }
    return a + b; // return a + b, bởi vì lúc này hoặc a hoặc b đã bằng 0.
}

Tìm UCLN sử dụng giải thuật Euclid
Cho a, b là hai số nguyên (giả sử a ≥ b), để tìm ước chung lớn nhất của hai số a và b ta cần thực hiện chia a cho b được thương q và số dư r (r ≥ 0) tức là a = b*q + r, khi đó ta có:
Cài đặt thuật toán sử dụng đệ quy.

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

Tất cả code chương trình:

#include <stdio.h>
#include <algorithm>
int gcd1(int a, int b){
    // Nếu a = 0 => ucln(a,b) = b
    // Nếu b = 0 => ucln(a,b) = a
    if (a == 0 || b == 0){
        return a + b;
    }
    while (a != b){
        if (a > b){
            a -= b; // a = a - b
        }else{
            b -= a;
        }
    }
    return a; // return a or b, bởi vì lúc này a và b bằng nhau
}

int gcd2(int a, int b){
    // Nếu a = 0 => ucln(a,b) = b
    // Nếu b = 0 => ucln(a,b) = a
    if (a == 0 || b == 0){
        return a + b;
    }
    // Lặp tới khi 1 trong 2 số bằng 0
    while (a*b != 0){
        if (a > b){
            a %= b; // a = a % b
        }else{
            b %= a;
        }
    }
    return a + b; // return a + b, bởi vì lúc này hoặc a hoặc b đã bằng 0.
}

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

int gcd4(int a, int b) {
    int tmp;
    while(b != 0) {
        tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

int main(){
    int a = 5, b = 9;
    printf("\ngcd1(%d, %d) = %d", a, b, gcd1(a,b));
    printf("\ngcd2(%d, %d) = %d", a, b, gcd2(a,b));
    printf("\ngcd3(%d, %d) = %d", a, b, gcd3(a,b));
    printf("\ngcd4(%d, %d) = %d", a, b, gcd4(a,b));
    printf("\ngcd5(%d, %d) = %d", a, b, std::__gcd(a,b));
}