최대공약수(Greatest Common Divisor)와 최소공배수(Least Common Multiple) 구하기 - 파이썬3

최대공약수 구하기

알고리즘을 풀다가 비슷한 로직이 필요했는데 잘 생각이 안나서 이번기회에 정리해두려고 한다. 보통 컴퓨터로 최대공약수를 구할 땐 유클리드 호제법이라는 방법을 많이 쓴다. 이미 기원전 300년에 검증된 로직이므로 그런게 아닐까 싶다. 유클리드 호제법은 다음과 같다.

 

1. 입력으로 두 수 m, n이 들어온다. (m>n)
2. n이 0이라면 m을 반환한다.
3. m이 n으로 나누어 떨어지면 n을 반환한다.
4. 위 2, 3번의 경우에 해당되지 않을 경우 n을 m으로, m을 n으로 나눈 나머지를 n에 대입하고 1번으로 돌아간다.

코드로 표현하면 다음과 같다.

def gcd(m, n):
    if m < n:
        m, n = n, m
    if n == 0:
        return m
    if m % n == 0:
        return n
    else:
        return gcd(n, m % n)

 

파이썬의 경우 표준라이브러리 math에서 gcd라는 이름으로 최대공약수를 구하는 함수를 제공하고 있다.

 

from math import gcd

print(gcd(78696, 19332))
# 36

 

최소공배수 구하기

최대공약수를 구했으면 최소공배수는 구하기 쉽다. 두 수 m과 n이 주어졌을 때 m * n / m과n의 최대공약수가 두 수의 최소공배수가 되기 때문이다. 코드로 표현하면 아래와 같다.

from math import gcd

def lcm(m, n):
    return m * n // gcd(m, n)

print(lcm(78696, 19332))
# 42259752

 

최소공배수를 구하는 데 있어서 각각의 수를 소인수분해한 뒤에 해당 요소들을 조합하여 하는 방법도 있지만 명백히 이것보다 느린 알고리즘이기 때문에 그냥 그런게 있다 라고만 생각하고 넘어가면 될 것 같다. 오랜만에 복습하는 시간이었다.