** 알고리즘 오답노트 12 (백준 - 2609)

최대공약수와 최소공배수

유클리드 호제법 을 이용한다...

• 두 수 a와 b (a > b)가 있다고 할 때, a와 b의 최대공약수 G1은 b와 a%b(a를 b로 나눈 나머지)의 최대공약수 G2와 같다. 반복해서 진행할때 오른쪽 값이 0이 되었을때 왼쪽 값이 곧 최대공약수이다.

ex) 32, 24 -> 24, 8 -> 8, 0 최대공약수는 8, 최대공약수는 8 * 4 * 3

import sys
x, y = map(int, sys.stdin.readline().split())
euclide = []
euclide.extend([x, y])

while euclide[1] > 0:
  euclide[0], euclide[1] = min(euclide), max(euclide) % min(euclide)
  
print(euclide[0])
print(int(euclide[0] * (x/euclide[0]) * (y/euclide[0])))

• 문제 링크