[프로젝트 오일러] 문제5 - 최소공배수

문제

영문

Smallest multiple

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

바로가기

 

한글

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

바로가기

 

해설

수학적 해결법

1부터 20까지의 수들의 최소공배수를 구하라는 문제입니다. 중학교 때 최소공배수를 구하던 정형화된 방식으로 풀어도 되지만, 그냥 20까지의 소수들을 생각한 다음, 각 소인수가 몇 번씩 곱해져야 하는지를 생각하면 됩니다.

• 2는 16으로 나누어 떨어지려면 4번 곱해져 있어야 합니다.
• 3은 9, 18로 나누어 떨어지려면 2번 곱해져 있어야 합니다.
• 5, 7, 11, 13, 17, 19는 한 번씩만 곱해져 있어도 됩니다.

따라서 정답은 2⁴ × 3² × 5 × 7 × 11 × 13 × 17 × 19가 됩니다!

 

파이썬(Python)

위 수학적 해결법을 프로그래밍 해봅시다! 우리에게 필요한 것은 두 가지입니다.

def makePrimeList(n):
    prime_list = []
    for x in range(2, n):
        isPrime = True
        for p in prime_list:
            if x%p == 0:
                isPrime = False
                break
        if isPrime:
            prime_list.append(x)

    return prime_list

첫 번째로는 20 이하의 소수 목록입니다. 다음과 같이 간단하게 구해줄 수 있습니다. 소수 구하는 자세한 방법에 대해선 프로젝트 오일러 7번을 참고해주세요!

 

두 번째는 해당 소수가 얼마큼 들어가있는지인데, 이는 해당 범위 내에서 그 소수로 된 가장 큰 거듭제곱이 무엇인지 알면 됩니다. 이는 로그 함수를 통해서 알 수 있습니다.

 

import math

n=20
prime_list = makePrimeList(n)
sqrt_n = int(n**(1/2))

i = 0
mul = 1

while prime_list[i] <= sqrt_n:
    p = prime_list[i]
    pow = int(math.log(n, p))
    mul *= p**pow
    i += 1

while i < len(prime_list):
    p = prime_list[i]
    mul *= p
    i += 1

print(mul)

소수가 제곱근 n보다 작을 경우에는 로그로 해당 소수를 얼만큼 거듭제곱하면 되는지를 확인합니다. 소수가 제곱근 n보다 클 때는 어차피 해당 소수 소인수가 딱 한번 들어가 있을 것이므로, 로그 계산 없이 그냥 곱해줍니다.

 

정답

232792560