알고리즘 - 유클리드 호제법

유클리드 호제법(Euclidean algorithm)은 최대공약수, 최소공배수를 구하는 가장 대중적인 알고리즘으로

호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 말한다.

2개의 자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라고 한다면 (단, a>b)
a와 b의 최대공야수는 b와 r의 최대공약수와 같다.

이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

이해하기 쉽게 예를 들어 108과 78의 최대공약수를 구해보면 아래와 같은 연산을 할 수 있다.

108 % 78 = 30 // 큰수를 작은수로 나누고 나머지를 구하기
78 % 30 = 18 // 위에서 나눈수(78)를 가져와 위의 나머지로 다시 나눠서 나머지 구하기
30 % 18 = 12 // 반복
18 % 12 = 6
12 % 6 = 0 // 나머지가 0이 되면 이때 나눈 수가 최대공약수(=6)

그렇다면 최소공배수는 어떻게 구할까?

최소공배수의 규칙에서 두 수 a,b가 있을 때 a * b = 최대공약수 * 최소공배수 라는 공식이 성립한다.

따라서 주어진 두수를 곱하고 최대공약수로 나눠준다면 그 수가 최소공배수가 될 것이다.

108 * 78 / 6 = 1404

이를 간단하게 코드로 구현해보면 다음과 같다.