GCD 알고리즘

 GCD(Greatest Common Divisor), 즉 최대 공약수를 구하는 방법에 대해 한 번 알아보고자 한다. 최대 공약수를 구하는 방법은 우리가 이미 초등학교, 중학교 때 배우기는 하였다. 두 수에 대해서 소수(Primary Number)를 나누어 주어 서로소로 만든 후, 나누어주었던 소수 집합을 모두 모아 곱해주면 그게 바로 최대 공약수였다. 그러나 이 방식을 컴퓨터에서 구현하기에는 아름답지 못한 방법이다. 우선 나누어주는 수가 소수인지 판단하는 데 시간을 소모하고, 두 수가 모두 해당 소수로 나누어지는 지 판단해야 한다. 이런 방식은 잠시 뒤로 밀어두고 우리는 유클리드 호제법을 이용하여 GCD를 구하고자 한다.

 유클리드 호제법의 가장 기본적이고 핵심적인 부분을 꼽자면 A, B라는 두 수에 대해 GCD는 A를 어떤 수 q로 나눈 나머지와 B의 GCD와 같다는 것이다. 증명은 다음과 같다.

 

 

 

실제로 코드로 작성하면 다음과 같이 작성할 수 있다.

 

int get_gcd(int a, int b) 
{
	int tmp, n;

	if (a < b) 
	{
		tmp = a;
		a = b;
		b = tmp;
	}

	while (b != 0) 
	{
		n = a % b;
		a = b;
		b = n;
	}

	return a;
}

 

 

오늘은 유클리드 호제법을 이용하여 GCD를 구하는 방법에 대해서 알아보았다. 이 것으로 글을 마친다.