[파이썬] 유클리드 호제법

최대공약수 (GCD: Greatest Common Divisior)

• 숫자 a와 b가 주어졌을 때, 공통된 약수 중에서 최대값을 의미

---

최소공배수 (LCM : Largest Common Multiple)

• 두 수 혹은 그 이상의 수들의 공통인 배수 중 가장 작은 수

---

유클리드 호제법

• 비교 대상 두 개의 자연수 n,m 에서 n을 m으로 나눈 나머지를 r이라고 했을 때
• GCD(n,m) = GCD(m, r)과 같고, r=0이면 m이 최대 공약수

import sys

a, b = map(int, sys.stdin.readline().split())

# 최대 공약수
def gdc(x, y):
    while y > 0:
        x, y = y, x % y
    return x

# 최소 공배수

def lcm(x, y):
    return x * y // gdc(x, y)


print(gdc(a, b))
print(lcm(a, b))