[Python]최대공약수, 최소공배수

알고리즘을 풀다가 최대공약수를 구해야 하는 문제가 나와, 별생각 없이 순진하게 아래와 같이 풀었다.

import sys

a, b = map(int, sys.stdin.readline().split())
x = max(a, b)
y = min(a, b)

while x % y != 0:
    z = x % y
    x = y
    y = z

print(a * b // y)

유클리드 호제법을 사용해서 간단하게 풀었다고 생각하고 넘어갔는데..

 

혹시나 해서 검색해보니 역시나 파이썬 math 라이브러리에는 최대공약수와 최소공배수를 구해주는 함수가 있었다!

 

그것도 유클리드 호제법을 이용해 최적화가 되어 있는!

 

적잖이 김이 빠지지만, 사용 방법은 아래와 같다.

import math

# 최대공약수
print(math.gcd(35, 65))
# 최소공배수
print(math.lcm(35, 65))

# 최대공약수
print(math.gcd(2, 4, 6, 8, 10))
# 최소공배수
print(math.lcm(2, 4, 6, 8, 10))

5
455
2
120

테스트에서 라이브러리를 마음껏 사용하게 해 주는지는 모르겠으나..

 

잊을만하면 느끼지만 수상할 정도로 수학 관련 함수가 잘 구성되어 있는 파이썬이다.