최대공약수와 최소공배수

최대공약수와 최소공배수를 구하는 방법은 중학교 수학 시간에 배웠던 걸로 기억한다.
중학교 수학 시간을 떠올리면서, 두 정수의 최대공약수와 최소공배수를 구하는 코드를 작성해보자.

1. 최대공약수 (Greatest Common Divisor, GCD)

최대공약수를 구하는 방법은 생각보다 간단하다.
두 정수를 소인수분해하여 공통되는 약수를 찾은 후 곱해주면 된다.
따라서, 최대공약수는 주어진 두 정수보다 작거나 같다고 말할 수 있다.

그렇다면, 최대공약수를 구하는 코드를 어떻게 작성해야 할까?
가장 먼저 생각할 수 있는 방법은 모든 경우의 수를 다 확인하는 방법일 것이다.
즉, 다음과 같이 주어진 두 정수 중 작은 정수부터 1까지 -1씩 감소시키면서 for문을 돌리면 최대공약수를 찾을 수 있다.

def gcd(a, b):
	if a < b:
    	min_Number = a
    else:
    	min_Number = b
    for i in range(min_Number + 1, 1, -1):
    	if a % i == 0 and b % i == 0:
        	result = i
            break
	return result

하지만, 위의 방법은 효율적인 방법이 아니다.
실제로 최대공약수 문제를 위 방법처럼 푼다면, 시간 초과로 인한 오답 처리가 될 것이다.
따라서 최대공약수를 구하는 코드를 작성할 때는 다음과 같이 작성하는 것이 좋다.

def gcd(a, b):
	while b != 0:
		result = b
		a, b = b, a % b
	return result

이 방식은 유클리드 호제법을 이용한 방법이다.
유클리드 호제법은 큰 수를 작은 수로 나누고, 그 나머지를 다시 제수로 나누는 반복적인 방법을 통해 최대공약수를 구하는 방법이다.

두 방법 중, 유클리드 호제법을 이용하여 최대공약수를 구하는 방법이 훨씬 간단하고, 훨씬 효율적이라는 것을 확인할 수 있다.

2. 최소공배수 (Least Common Multiple, LCM)

최대공약수를 공부할 때, 항상 짝궁처럼 같이 나오는 것이 바로 최소공배수이다.
최대공약수가 두 정수의 공통된 약수 중 가장 큰 수였다면, 최소공배수는 두 정수의 공통된 배수 중 가장 작은 수이다.
최소공배수를 구하는 방법은 두 정수를 소인수분해 한 뒤, 구해진 모든 인수를 곱하면 된다.

최소공배수를 구하는 코드는 앞서 작성한 최대공약수 코드를 이용한다면 쉽게 작성할 수 있다.
그 이유는 최소공배수와 최대공약수 사이의 관계에 대해서 조금만 생각해본다면 쉽게 알아낼 수 있다.
간단한 예시를 통해서 최소공배수와 최대공약수 사이의 관계를 확인해보자.

21과 12의 최소공배수를 찾는다고 가정해보자.

$21 = 3 * 7$
$12 = 2 * 2 * 3$

두 수의 최대공약수는 3이다.
최소공배수는 두 수를 소인수분해 한 뒤 모든 인수를 곱하면 된다고 했으므로, 84라는 값을 얻을 수 있다.

$84 = 2 * 2 * 3 * 7$

최소공배수의 인수를 확인해보면, 주어진 두 수를 곱한 값에서 최대공약수를 나눠준 값과 같다는 것을 확인할 수 있다.
즉, 주어진 두 수를 곱한 뒤, 두 수의 최대공약수로 나누어주면 최소공배수를 구할 수 있다.

따라서 최대공약수를 구할 수 있다면, 다음 코드와 같이 최소공배수를 구할 수 있다.

def lcm(a, b):
	gcd_Number = gcd(a, b)
   	result = a * b // gcd_Number
   	return result