유클리드 호제법(Euclidean algorithm)

유클리드 호제법은 2개의 자연수 사이의 최대공약수를 구할 때 사용하는 알고리즘이다.


2개의 자연수 a, b(a > b)가 있고 a % b = r 이라고 한다면 a, b의 최대공약수는 a, r의 최대공약수와 같다. 이 성질을 이용해 b를 r로 나눈 나머지 r’을 구하고 다시 r을 r’으로 나눈 나머지를 구하는 과정을 반복해서 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수라고 한다.

최대 공약수를 구하기 위해 a, b(a > b)에 대하여 2부터 b까지 모든 수를 나누는 방법이 있겠으나 수가 커지면 시간이 오래걸린다.
하지만 유클리드 호제법은 mod연산을 통해 빠르게 수를 줄여나감으로 기존의 방법보다 효율적이다.

wikipedia의 예시를 보자.

79696과 19332의 최대공약수를 구하는 예시다.

78696 ＝ 19332×4 ＋ 1368
19332 ＝ 1368×14 ＋ 180
1368 ＝ 180×7 ＋ 108
180 ＝ 108×1 ＋ 72
108 ＝ 72×1 ＋ 36
72 ＝ 36×2 ＋ 0
따라서, 최대공약수는 36이다.

매우 간결하다.

int gcd(int a, int b){
	return b ? gcd(b, a % b) : a;
}

재귀함수는 쓸모가 많다.