Tìm ước chung lớn nhất của 2 số

Ước chung lớn nhất (GCD - Greatest Common Divisor) của 2 số nguyên \(a\) và \(b\) là số nguyên lớn nhất \(d\) thỏa mãn cả \(a\) và \(b\) đều chia hết cho \(d\).

Thuật toán trừ dần

Mã nguồn (C):

int gcd(int a, int b) {
    while (a != b) {
        if (a > b) a = a - b;
        else b = b - a;
    }
    return a;
}

Thuật toán Euclide

Công thức

Công thức Euclide để tính ước chung lớn nhất:

Trong đó \(a \bmod b\) là số dư khi chi \(a\) cho \(b\).

Cài đặt đệ qui (C)

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

Cài đặt không đệ qui (C)

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

Thuật toán nhị phân (Binary GCD Algorithm)

Thuật toán gồm các bước như sau:

• Nếu a = b thì gcd(a, b) = a = b.
• gcd(0, v) = v, gcd(u, 0) = u.
• Nếu cả u và v đều chẵn thì gcd(u, v) = 2*gcd(u/2, v/2).
• Nếu u chẵn và v lẻ thì gcd(u, v) = gcd(u/2, v). Tương tự, nếu u lẻ và v chẵn thì gcd(u, v) = gcd(u, v/2).
• Nếu cả u và v đều lẻ và u > v thì gcd(u, v) = gcd((u-v)/2, v). Và ngược lại.
• Lặp lại các bước trên.

Độ phức tạp : \(O(\log(\max(u, v))^2)\)

Cài đặt đệ qui (C):

int gcd(int a, int b) {
    if (a == b) return a;
    else if (a == 0 || b == 0) return a | b;
    else if (!(a&1) && !(b&1)) return gcd(a>>1, b>>1)<<1;
    else if (!(a&1) && b&1) return gcd(a>>1, b);
    else if (a&1 && !(b&1)) return gcd(a, b>>1);
    else if (a > b) return gcd((a-b)/2, b);
    else return gcd((b-a)/2, a);
}