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

문제

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

풀이

유클리드 호제법을 이용하면 소인수분해 없이 최대공약수와 최소공배수를 구할 수 있다.

유클리드 호제법은 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)가 된다.

Python 코드

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)