[Python]백준 BaekJoon.AC 2609 : 최대공약수와 최소공배수(유클리드 호제법)

 

 

유클리드 호제법을 이용해 최소공약수와 최대공배수를 구하라는 문제.

두 수 중 큰 수를 작은 수로 나누고, 그 나머지로 원래 큰 수를 대신한다.

둘 중 한쪽이 0이 될 때까지 실행하며 다른 값이 최대공약수다.

원래 두 수를 곱한 값에서 최대공약수를 나누면 최소공배수가 된다.

 

원리는 알지만 늘 신기하다!ㅋㅋㅋ

그리고 그 원리를 늘 다시 까먹는다.

다시 공부하고 신기해하고 반복..

 

최소공배수 구하는 건 새로워서 이 방법으로 해봤다.

참신하고 신기하다..

 

 

 

A, B = map(int, input().split())
copyA, copyB = A, B

while not (A==0 or B==0):
    if max(A, B) == A:
        A = A % B
    else:
        B = B % A

result = max(A, B)
print(result)
print(copyA * copyB // result)