알고리즘 - 유클리드 호제법을 이용한 최대공약수와 최소공배수 구하기 (Using Euclidean Algorithm to Get GCD and LCM)

유클리드 호제법

유클리드 호제법 (Euclidean Algorithm) 이란 두 수의 최대 공약수 (Greatest Common Divisor, GCD) 를 구하기 위한 알고리즘으로써, 시간 복잡도 O(log N) 의 시간 동안 두 수의 최대 공약수를 구할 수 있다. 유클리드 호제법을 이용한 최대 공약수 구하기는 다음과 같다.

 

1. 두 수, a와 b중 더 큰 수를 더 작은 수로 나눈다. (a가 더 크다고 가정하자)
2. 이후 구해진 나머지 값으로 b를 나눠준다. (즉 a / b의 나머지 값이 c라고 했을 때, b / c)
3. 이후 구해진 나머지 값으로 c를 나눠준다. (즉 b / c의 나머지 값이 d라고 했을 때, c / d)
4. 이 과정을 나머지 값이 0이 될 때까지 반복해준다. 나머지가 0이 되었다면, 나눠준 값이 곧 최대 공약수이다.

 

예를 들어, 20과 12의 최대 공약수를 구한다고 가정하자. 과정은 다음과 같다.

 

1. 20 / 12 를 해준다. 나머지는 8이다.
2. 12 / 8 을 해준다. 나머지는 4이다.
3. 8 / 4 를 해준다. 나머지는 0이다.
4. 나머지가 0이니 4가 20과 12의 최대 공약수이다.

이 방식을 사용하면 최대 공약수를 쉽게 구할 수 있다.

 

최대 공약수와 최소 공배수의 관계

두 수의 최소 공배수 (Least Common Multiple, LCM) 를 구하기 위해선 두 수의 곱을 최대 공약수로 나눠주기만 하면 된다. 따라서 최대 공약수와 최소 공배수를 구하는 알고리즘은 다음과 같다.

 

def gcd_euclidean(a, b):
  a, b = max(a, b), min(a, b)
  while b != 0:
    a, b = b, a % b
  return a

def lcm(a, b):
  return int(a * b / gcd_euclidean(a, b))

a = 12
b = 20
print(gcd_euclidean(a, b))
print(lcm(a, b))

 

출력

 

4
60

 

참고로 파이썬의 기본 내장 라이브러리인 math 모듈의 함수 중 gcd라는 함수는 두 수의 최대 공약수를 출력하는 함수이다. 유클리드 호제법을 구현하는 게 귀찮다면 사용해주도록 하자.

 

출처

https://namu.wiki/w/%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98

https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95

https://m.blog.naver.com/PostView.nhn?blogId=writer0713&logNo=221133124302&proxyReferer=https:%2F%2Fwww.google.com%2F