프로젝트 오일러 005

여러 수들의 공통 최소공배수

이 문제는 중학교 수준에서 1, 2, 3, 4, ··· , 19, 20 의 최소 공배수를 찾는 문제입니다. a, b, c의 최소 공배수는 a, b의 최소 공배수를 x 라 할 때, x, c의 최소공배수와 같습니다. 즉, 연속한 자연수를 앞에서부터 누적하여 최소공배수 연산으로 접어나가면 됩니다.

두 수 A, B의 최소 공배수를 구하기 위해서는 최대 공약수를 구해야 합니다. 두 수의 최대공약수를 g라 할 때 A = g × a, B = g × b로 표현할 수 있고, 그렇다면 최소공배수는 이렇게 표현됩니다: l = g × a × b

리듀스(reduce)나 폴드(fold)는 2항 연산으로 리스트의 앞에서부터 같은 연산을 반복하여 리스트의 값을 하나의 값으로 축약하는 연산 방법입니다. 초기값을 하나 정하고, 리스트의 앞에서부터 값을 골라 연산을 적용합니다. 다시 그 결과와 그 다음 원소를 연산하고, 이 과정을 끝까지 반복하는 것입니다.

예를 들어 0을 초기값으로 더하기를 리스트에 대해 리듀스하면 앞에서부터 계속 더한 합계를 구하게 되고, 1을 초기값으로 곱하기를 반복하여 누적 곱을 구하게 됩니다. 둘 중 큰 값을 고르는 연산을 반복하면 최대값을 구할 수 있고, 1을 더하는 연산을 반복하면 개수를 셀 수도 있겠죠.

우리가 해야할 일은 두 수의 최소 공배수를 구하는 연산을 계속하는 것입니다.

from functools import reduce 


def gcd(a, b):
	if a < b:
		return gcd(b, a)
	q, r = divmod(a, b)
	if r == 0:
		return b
	return gcd(b, r)

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


print(reduce(lcm, range(1, 21)))

Julia에는 gcd, lcm이 기본 라이브러리에 포함되어 있어서 다음과 같이 풀 수 있습니다.

foldl(lcm, 1:20) |> println