문제
유클리드 호제법을 이용하면 소인수분해 없이 최대공약수와 최소공배수를 구할 수 있다.
유클리드 호제법은 a, b 두 수가 있으면, a, b의 최대공약수와 b와 a를 b로 나눈 나머지 r의 최대공약수는 같다는 점을 이용한다.
이를 반복하여 b를 r로 나눈 나머지로 r을 나누는 반복을 나머지가 0이 될 때까지 반복한다.
나머지가 0이 되기 전 단계의 나머지(나머지가 0이 될 때 나누는 수)가 최대 공약수가 된다.
이렇게 구한 최대공약수는 최소공배수를 구하는대에 사용할 수있다.
a, b 두 수가 있으면,
a x b = gcd(a, b) x lcm(a, b) 이므로,
lcm(a, b) = (a x b) / gcd(a, b)가 된다.
import sys
input = sys.stdin.readline
a, b = map(int, input().split())
x, y = a, b
while y > 0:
x = x % y
x, y = y, x
print(x) # gcd(a, b)
print(a*b/x) # lcm(a, b)