최대공약수와 최소공배수

최대 공약수와 최소 공배수

최대 공약수와 최소 공배수를 계산하는 방법에 대해서 알아보자.

최대 공약수와 최소 공배수가 나오는 제법 유명한 문제로는 프로젝트 오일러의 5번 문제는 다음과 같다.

1~10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다. 그러면 1~20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?

이 문제는 결국 20이하의 자연수 전체의 최소 공배수가 얼마인지를 묻는다. 참고로 이 문제의 답은 매우 큰 수이기 때문에 C와 같이 큰 수를 기본적으로 지원하지 않는 언어에서는 큰 수의 곱셈을 계산하는 별도의 자료 구조와 알고리듬이 필요할 것이다. 이 글은 당연희 파이썬으로 푸는 방법을 소개한다.

두 A, B 의 최소 공배수를 구하는 방법은 다음과 같다.

두 수 A, B의 최대공약수를 g라 한다.
이 때, $$A = g \times a, B = g \times b$$라 둘 수 있고, a, b 는 서로 소이다.
따라서 두 수 A, B의 최소공배수는 $$g \times a \times b$$가 된다.

그렇다면 세 개 이상의 수의 최소 공배수는 어떻게 구할까?

A, B, C 세 수의 최소 공배수를 구할 때,
먼저 A, B 의 최소 공배수를 L 이라 하자.
이 때, L, C 의 최소 공배수를 구하면 그 값이 A, B, C의 최소 공배수가 된다.

따라서 우리에게 만약 두 수의 최소 공배수를 구할 수 있는 함수가 있다면, 이를 1..20의 리스트에 차곡차곡 적용하여 하나의 값으로 접으면 20개 수의 최소 공배수를 구할 수 있게 된다. 무슨 말인고 하니, 1, 2, 3 .... 20의 수열이 있을 때,

우선 1, 2 의 최소 공배수를 구한다. (2)
그리고 1의 답인 2와, 수열의 그 다음 원소인 3의 최소공배수를 구한다. 6이며, 이 값은 이제 1, 2, 3의 최소 공배수이다.
이와 같은 식으로 4, 5, 6... 등에 대해서 최소공배수를 구하는 값을 누적 계산한다.
20까지 계산하면 답이된다.

최소 공배수를 구하려면 먼저 최대 공약수를 구해야 한다. 최대 공약수는 유클리드의 호제법을 이용하여 간단히 구할 수 있다.


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

최대 공약수는 두 수의 최대 공약수만 구하고나면 다음과 같이 쉽게 해결된다.


def lcm(a, b):
    g = gcd(a, b)
    x = a // g
    y = b // g
    return g * x * y

이제 최종적인 답은 다음과 같이 구할 수 있다. 리스트 접기를 위해 reduce를 사용한다. (참고로 reduce는 파이썬 3에 와서는 functools로 빠져버렸지만, 파이썬의 리스트 연산에 있어서 절대 빼놓을 수 없는 중요한 함수인 만큼 잘 알아두도록 한다.)


from functools import reduce 

def eu05():
    result = reduce(lambda x, y: x * y, range(1, 21), 1)
    print(result)

53Percent

최대공약수와 최소공배수