[백준] 1934번 최소공배수 - PYTHON

[백준] 1934번

최소공배수

유클리드 알고리즘

백준 1934번

최소공배수를 구하는 것은 간단한 문제이다.

A와 B의 최대공약수를 먼저 구하고 A와 B의 곱을 최대공약수로 나누면
최소공배수를 구할 수 있다.

G = gcd(A, B)
L = A*B / G

일단 최대 공약수는 반복문을 통해서 쉽게 구하는 방법이 있다.

또는 파이썬의 math 라이브러리의 gcd 함수를 이용하는 방법이 있다.

이 문제에서는 유클리드 알고리즘을 통해서 최대 공약수를 구한다.

위와 같은 방식으로 최대 공약수를 구한 뒤에 최소 공배수를 구하는 식을 통해
입력된 두 자연수의 최소 공배수를 구할 수 있다.

최종 소스코드는 아래와 같다.