간단한 GCD 알고리즘(Euclid 호제법)

간단한 GCD(최대공약수)를 구하는 코드입니다.

여기에 이용되는 방법 중 하나가, 유클리드 호제법이라는 방법입니다.

A, B가 있을 때((A > B)라고 가정) A를 B로 나눴을 때 나눠지면 B가 최대 공약수입니다.

하지만 나누어 떨어지지 않으면 A를 B로 B를 A % B로 치환하고서 다시 A % B를 실행합니다.

계속 반복했을 때 A % B = 0이 됐을 때의 B값이 GCD값이 됩니다.

12와 9를 기준으로 보겠습니다.

A % B = 3 입니다.

나누어 떨어지지 않았기 때문에 A = B, 즉 9가 되고 B = A%B, 즉 3이 됩니다.

9와 3을 가지고 다시 돌립니다.

A%B = 0

그럼 여기서 나오는 3(B의값)이 최대공약수라는 것을 알 수 있습니다.

최대공약수가 쓰이는 부분은 많지만 가장 기본적인 경우는 분수의 연산시에 필요합니다.

15 / 20 은 3 / 4로도 표현될 수 있습니다.

이 유클리드 호제법을 이용한 GCD 구하는 코드는 다음과 같습니다.

int Euclid(int a, int b)
{

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

a % b가 0이 되면 그것을 리턴해주고

나누어 떨어지지 않으면 다시 Euclid 함수를 호출하는 것입니다.

처음의 if와 else의 쌍은 a가 b보다 클 수도 있고 작을 수도 있기 때문에 추가해 놓았습니다.

이 코드를 없애고 싶으시면 항상 a를 b보다 크게해서 한다거나 하시면 됩니다.