백준 2609 최대공약수와 최소공배수

• 유클리드 호제법 공부하기
  • x%y 를 r이라고 할 때, x와 y의 최대공약수는 y와 r의 최대공약수와 같음
    • r이 0이 될 때까지 x = y, y = r을 반복. r이 0이면 그 때의 y가 최대공약수
  • 최소공배수는 x * y // r
    • 공통 약수는 한 번씩 곱해주고, 공통이 아닌 약수를 모두 한 번씩 곱해주면 최소공배수

x, y = map(int, input().split())
# 최대공약수 구하기
def divide(x, y):
    while True:
        r = x % y
        if r == 0:
            return y
        else:
            x = y
            y = r
r = divide(x, y)
print(r)

# 최소공배수 구하기
def multiple(x, y, r):
    return (x * y) // r

print(multiple(x, y, r))