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

✔ 풀이를 위한 아이디어

• 유클리드 호제법 (Euclidean-algorithm)
• 최소공배수 = 두 자연수의 곱 / 최대공약수
  
  

✔ 코드

import sys

a, b = map(int, sys.stdin.readline().split())

if b > a:
    a, b = b, a

x = a
y = b

while y != 0:
    tmp = x % y
    x = y
    y = tmp

print(x)
print(int((a * b)/x))

• 두 자연수의 최대공약수를 구하는 가장 일반적인 방법은 소인수분해를 통해 공통의 인수를 찾는 것이다. 그러나 이는 숫자가 커지게 되면 비효율적이므로 다른 방법이 필요하다.
• 유클리드 호제법(Euclidean-algorithm)이란 큰수를 작은수로 나눈 나머지가 계속해서 큰수를 대체하다가, 최종적으로 나머지가 0이 나왔을 때 작은수가 최대공약수가 되는 알고리즘이다. 시간복잡도가 O(logN)라고 한다.
• 이산수학 시간에 배웠던 것 같은 기억이 있는데, 기원전 300년 경에 발견된 가장 오래된 알고리즘이다.
• 두 수와 최대공약수를 알고 있으면, 그 두 수의 최소공배수도 간단하게 구할 수 있다.
• 삼항 연산자를 활용하여 재귀호출로 구현할 수도 있다.

✔ 관련 개념

• 유클리드 호제법 (Euclidean-algorithm): https://myjamong.tistory.com/138, https://velog.io/@yerin4847/W1-유클리드-호제법