[백준 2609번] 최대공약수와 최소공배수 (파이썬/python)

https://www.acmicpc.net/problem/2609

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

유클리드 호제법을 이용해 최대공약수를 구할 수 있고

최소공배수는 두 값의 곱 / 최대공약수 임

 

https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95

갓무위키에 유클리드 호제법에 대한 내용이 참 정리가 잘 돼있습니다.

 

 

import sys
 
input = sys.stdin.readline
 
 
def gcd(a, b):
    r = a % b
 
    if r == 0:
        return b
    else:
        return gcd(b, r)
 
 
num = list(map(int, input().split()))
num = sorted(num, reverse=True)
g = gcd(num[0], num[1])
l = num[0] * num[1] // g
print(g, l, sep="\n")