[Python] BJ.2609 최대공약수와 최소공배수

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

풀이

최대공약수 : 두 수의 약수 중에서 가장 큰 수. 유클리드 호제법에 의해 쉽게 구할 수 있다.

최소공배수 : 두 수의 공통된 배수 중에서 가장 작은 수. 주어진 두 수의 곱에서 두 수의 최대공약수를 나눈 값과 같다.

 

def GCD(a, b):
	while b:
    	a, b = b, a % b
    return a
    
def LCM(a, b):
	return a * b // GCD(a, b)

a, b = map(int, input().split())
print(GCD(a, b))
print(LCM(a, b))