문제
소스코드
import sys
def gcd(a, b):
if a % b == 0:
return b
else:
return gcd(b, a % b)
a, b = map(int, sys.stdin.readline().split())
g = gcd(max(a, b), min(a, b))
l = a * b // g
print(g, l, sep="\n")
풀이
-
두 수 A, B의 최대공약수를 G, 최소공배수를 L이라고 하면 다음 식이 성립한다.
AB=LG -
유클리드 호제법 알고리즘
- A, B의 최대공약수를 구하기 위해서 A를 B로 나눈 나머지 R1을 구합니다.
- B를 R1으로 나눈 나머지 R2를 구합니다.
- R1을 R2로 나눈 나머지 R3를 구합니다.
- 이 과정을 반복하여, 어느 한 쪽이 나누어떨어지면 이 직전 얻은 나머지가 최대공약수이다. -
위 두가지 정보를 활용하여 최대공약수는 재귀함수, 최소공배수는 최대공약수를 구한뒤 A,B,G를 식에 대입하여 최소공배수를 계산한다.
