Python으로 최소공배수(LCM) 구하는 방법 완벽 정리

두 개(또는 그 이상)의 수에 대한 최소공배수(LCM, Least Common Multiple)는 해당 수들 모두로 나누어 떨어지는 가장 작은 양의 정수를 의미합니다.

가장 직관적인 방법은 다음과 같습니다. 먼저 주어진 두 수 중 더 큰 수를 찾고, 그 수부터 시작하여 두 수 모두로 나누어 떨어지는 첫 번째 수를 찾을 때까지 값을 하나씩 증가시키며 확인합니다. 이렇게 찾은 수가 바로 LCM입니다.

예제 코드

x = 12
y = 20

if x > y:
    greater = x
else:
    greater = y

while True:
    if (greater % x == 0) and (greater % y == 0):
        lcm = greater
        break
    greater += 1

print("LCM of {} and {}={}".format(x, y, lcm))

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

LCM of 12 and 20=60

더 효율적인 방법: GCD 활용하기

반복문으로 하나씩 확인하는 방법은 수가 커지면 시간이 오래 걸릴 수 있습니다. 이럴 때는 최대공약수(GCD)를 이용하면 훨씬 빠르게 LCM을 계산할 수 있습니다. 두 수의 곱을 최대공약수로 나누면 최소공배수가 된다는 수학적 성질을 활용하는 것입니다.

import math

def lcm(x, y):
    return x * y // math.gcd(x, y)

print(lcm(12, 20))  # 출력: 60

또한 Python 3.9 이상 버전에서는 math.lcm() 함수를 기본으로 제공하므로, 별도의 계산 없이 바로 사용할 수 있습니다.

import math

print(math.lcm(12, 20))  # 출력: 60

정리

작은 수라면 반복문 방식으로 충분하지만, 큰 수나 여러 개의 수를 다룰 때는 math.gcd() 또는 math.lcm()을 활용하는 것이 성능과 가독성 면에서 훨씬 유리합니다.