$$ GCD(a,b) = GCD(b, r) $$

Greates Common Divisor

줄여서 GCD 라고 한다. 두 수 a와 b의 최대공약수 g는 a와 b의 공통된 약수중에서 가장 큰 정수이다. 최대공약수가 1인 두 수를 서로소(Coprime)이라고 한다.

일반적으로 가장쉬운 방법은 2부터 min(a,b)까지 모든 정수로 나누어보는 방법이다.

근데 위 방법보다 더 효율적인 알고리즘이 있다. 바로 그게 유클리드 호제법이라는 알고리즘이다.

유클리드 호제법

a를 b로 나눈 나머지를 r이라고 했을때, GCD(a,b) = GCD(b,r)과 같다.

GCD(b,r)에서 r이 0이면 그 때 b가 최대 공약수이다.

GCD (24, 16) = GCD(16,8) = GCD(8, 0) = 8;

int GetGCD(int _A, int _B)
{
	if (_B == 0)
	{
		return _A;
	}
	else
	{
		return GetGCD(_B, _A % _B);
	}
}