백준 2869[Python]

유클리드 호제법을 사용하여 최소공배수와 최대공약수를 구했다.

유클리드 호제법이 뭐냐하면

When I first learned this method, I was curious why is this possible.
But think about it.
The given number is M and N.
We first divide M by N.

If the remainder is not 0, we test whether R1 is GCD.

If R1 is 0, then

다음과 같이 R1이 최대공약수가 된다.
결국 호제법은 나누었을 때, 나머지가 최대공배수가 될 수 있나를 보는 것이라고 할 수 있다.

코드로 표현하면 다음과 같다.

M,N = map(int,input().split())
mm,nn = M,N
while(M%N!=0):
  M,N = N,M%N
max = N
min = mm*nn//max
print(max)
print(min)