[파이썬] 백준 - 2609: 최대공약수와 최소공배수

---

문제

2609번: 최대공약수와 최소공배수

---

풀이

유클리드 호제법을 이용하였다.

재귀함수를 통해 계속 나누어 최대공약수를 구하는 방법.

이 방법으로 최소공배수도 쉽게 구할 수 있다.

 

a, b = map(int, input().split())

def gcm(x, y):	# 최대공약수
    while y:	# 나머지가 0일 때 까지
        x, y = y, (x % y)	# 재귀
    return x

def lcm(x, y):	# 최소공배수
    result = (x * y) // gcm(x, y)	# x, y의 곱을 최대공약수로 나눠줌
    return result

print(gcm(a, b))
print(lcm(a, b))