Greatest Common Divisor - Ước chung lớn nhất

 

Greatest Common Divisor - GCD

Hay còn gọi là Ước Chung Lớn Nhất là một thuật ngữ quan trọng trong toán học nói chung và tin học nói riêng. Trong bài này mình sẽ giải đáp giúp các bạn về khái niệm của GCD và cách tìm GCD của 2 số sao cho độ phức tạp tối ưu nhất có thể.

Khái niệm GCD

Chúng ta định nghĩa GCD của hai số nguyên không âm như sau:

Với hai số nguyên không âm $a$ và $b$, $GCD(a, b)$ là số nguyên lớn nhất là ước của cả $a$ và $b$.

 

 Có một điều ta cần chú ý: không tồn tại $GCD(a, b)$ trong trường hợp $a = 0$ và $b = 0$.

 

Cách tìm GCD của 2 số nguyên không âm

Thuật toán trâu bò:

Dựa theo bản chất, chúng ta có được một cách tìm GCD đơn giản như sau:

Gọi $x = min(a, b)$, xét các số từ $x$ về $1$, lấy số đầu tiên là ước của cả $a$ và $b$.

 

Cách làm này khá đơn giản và dễ hiểu, tuy nhiên nó khá chậm. So với các thuật toán $O(logN)$ hay $O(log(logN))$ hiện nay thì một thuật toán $O(N)$ như thế này tỏ ra khá lép vế. Tuy nhiên nếu bạn vẫn tò mò về code của thuật toán, sau đây là Implement của nó:

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

Phương pháp Euclid:

Phương pháp Euclid được mô tả như sau:

Nếu $a = 0$, $GCD(a, b) = b$. Nếu $b = 0, GCD(a, b) = a$. Nếu cả hai đều dương, lấy số lớn hơn trừ cho số bé. Lặp lại quá trình cho tới khi 1 số bằng $0$.

Về cơ bản, thuật toán này có phần nhanh hơn thuật toán trâu bò ở trên, tuy nhiên nó vẫn RẤT chậm. Với những cặp số có một số quá lớn với những số còn lại thì độ phức tạp cũng chẳng khác là bao.

Độ phức tạp của thuật toán: $O(a \times b)$

Implement của thuật toán:

 

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

Phương pháp Euclid cải tiến:

Ta nhận ra khi lặp lại $max -= min$ nhiều lần sẽ cho ra kết quả đúng bằng $max %= min$, chúng ta có thể cải tiến phương pháp Euclid như sau:

Nếu $a = 0$, $GCD(a, b) = b$. Nếu $b = 0, GCD(a, b) = a$. Nếu cả hai đều dương, lấy số lớn hơn CHIA DƯ cho số bé. Lặp lại quá trình cho tới khi 1 số bằng $0$.

 

Độ phức tạp của thuật toán: $O(log(max(a, b)))$. 

Implement của thuật toán:

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

Một vài hàm tính GCD có sẵn trong ngôn ngữ lập trình:

Trong C++:

int main(){
	cout << std::__gcd(a, b) << '\n'; // C++17
	cout << (a * b) / std::__detail::__lcm(a, b) << '\n'; // C++17
	cout << std::gcd(a, b) << '\n'; // C++20
}

Trong Java: 

public static int GCD(int a, int b)
{  
	// create 2 BigInteger objects  
	BigInteger big1= new BigInteger(a);    
	BigInteger big2= new BigInteger(b);    
	BigInteger bigVal= big1.gcd(big2);
	return Integer.parseInt(bigVal.toString());
}

Trong Python:

print (math.gcd(3, 6))

Chúc bạn thành công.