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

최대공약수와 최소공배수..
공부를 할 때나 연습을 할 때 정말 정말 많이 했던 문제들이다.
원래는 a, b 각각의 약수에서 공통되는 가장 큰 수를 찾는 방법으로 생각했다.

가장 단순하게 생각했을 때 내 머리로 바로 생각난 방법이라서,
일단 해봤지만 뭔가 다른 더 효율적인 방법이 있을 것 같아 찾아봤고

다양한 방법이 있었지만 유클리드 호제법을 선택하게 되었다.

유클리드 호제법도 정말 많이 사용하는 방법이었고, 내가 이 방법으로도 해봤는지 기억이 안나서 하게 되었다.

 

n = list(map(int, input().split()))
n.sort(reverse=True)

b = n[0]
gcd = n[1]
lcm = 1

# 최대공약수
while True:
    if (b%gcd != 0):
        temp = b%gcd
        b = gcd
        gcd = temp
    else:
        break

# 최소공배수
lcm = (n[0] * n[1])//gcd

print(gcd)
print(lcm)

유클리드 호제법이란,
2개의 자연수(또는 정수) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면
(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때의 수를 구했다.

최소공배수의 성질
a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다.

이 성질을 이용하여 최소공배수를 구했다.

끝!