[Python] 1934. 최소공배수

문제

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)

출력

첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.

예제 입력 1 

3
1 45000
6 10
13 17

예제 출력 1 

45000
30
221

 

---

위 문제를 푸는 방식에는 두 가지 방식이 존재한다.

첫 번째 방법으로는 Python 내장 라이브러리인 math 라이브러리를 이용하여 간단하게 정답을 구하는 방법이다.

 

먼저, 첫 번째 방법을 설명하기 전에 최대공약수와 최소공배수의 정의를 살펴보자.

• 최대공약수(GCD; Greatest Common Divisor)
  
  • 모든 정수들의 약수가 되는 양의 정수 가운데 가장 큰 수
• 최소공배수(LCM; Least Common Multiple)
  • 여러 개의 정수 모두의 배수가 되는 음이 아닌 정수 가운데 가장 작은 수

 

위 예제에 있는 6, 10을 이용하여 간단히 설명하자면,

• 6의 약수
  • 1, 2, 3, 6
• 10의 약수
  • 1, 2, 5, 10

둘의 공통 약수 중 가장 큰 수인 2가 최대공약수가 되고,

• 6의 배수
  • 6, 12, 18, 24, 30, 36 ...
• 10의 배수
  • 10, 20, 30, 40, 50, 60 ...

둘의 공통 배수 중 가장 작은 30이 최소공배수가 된다.

 

다시 첫 번째 방법으로 돌아와 어떻게 최소공배수를 구하는 지 코드를 보면,

import sys, math

n, m = map(int, sys.stdin.readline().split())
print(math.lcm(n, m))

math 라이브러리에 있는 lcm 함수를 이용하여 구할 수 있다.

 

두 번째 방법으로는 math 라이브러리를 사용하지 않고, 유클리드 호제법을 이용한 방법이 있다.

이는, 최대공약수와 최소공배수의 관계를 알아야 한다.

위에서는 약수와 배수를 각각 나열해서 각각을 찾았지만, 실제로 최대공약수와 최소공배수를 찾는 방법은 아래 방법이다.

60, 48의 최대공약수, 최소공배수를 구해보면

공약수를 이용하여 소수가 나올 때까지 나눈 뒤 공약수들을 곱해서 나온 (2 * 2 * 3) 값 12가 최대공약수이고,

공약수들과 서로소까지 곱해서 나온 (2 * 2 * 3 * 5 * 4) 값 240이 최소공배수이다.

이를 통해 최대공약수와 최소공배수의 관계를 설명하자면 아래와 같다.

G = 최대공약수

a, b = 서로소

위를 예시로 들자면 G = 12, a = 5, b = 4이다. 즉, A를 G로 나눈 값의 몫이 a, B를 G로 나눈 값의 몫이 b 이다.

최소공배수를 L이라 하면, 위에서 최소공배수를 구하는 식에 대입했을 때,

L = G * a * b 가 된다.

여기서 G * a = A, G * b = B 이므로, 양 변에 G를 곱해주면,

L * G = A * B 로 표현할 수 있다.

길게 설명했지만, 결정적으로 최대공약수와 최소공배수의 관계로 최소공배수는 두 수의 곲을 최대공약수로 나눈 값이라는 것을 알 수 있다.

 

이제 유클리드 호제법이 무엇인 지 간단하게 알아보자.

유클리드 호제법

두 양의 정수 a, b(a > b)에 대하여 a = bq + r(0 <= r < b)이라 하면, a, b의 최대공약수는 b, r 의 최대공약수와 같다.
즉, gcd(a, b) = gcd(b, r) r = 0이라면, a,b의 최대공약수는 b가 된다.

 

간단하게 예시를 들자면,  b가 0이 될 때까지,

a = b

b = a % b (a로 나눈 나머지)

가 되도록 하는 것이다. 6, 8을 위에 대입하게 되면

a = 6, b = 8
a = 8, b = 8 % 6 = 2
a = 2, b = 2 % 2 = 0
최대공약수 = 2

이렇게 식이 진행하는 것이다. 이를 Python 코드를 이용하여 만들면 두 가지 방식을 이용할 수 있다.

1. 반복문

def Euclidean(a, b)
	while b:
    	a = b
        b = a % b
    return a

 

2. 재귀문

def Euclidean(a, b):
	if b == 0:
    	return a
    return Euclidean(b, a % b)

 

이를 이용하여 최종적으로 최소공배수를 구하는 코드는 아래와 같다.

import sys

def Euclidean(a, b):
    if b == 0:
    	return a
    return Euclidean(b, a % b)

T = int(sys.stdin.readline())

answer = []

for _ in range(T):
    n, m = map(int, sys.stdin.readline().split())
    gcd = Euclidean(n, m)
    lcm = (n * m) // gcd
    answer.append(lcm)