5. Smallest multiple

projecteuler.net/problem=5

Problem 5 - Project Euler

 

 

문제는 다음과 같습니다.

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?

2520은 1에서 10 사이의 모든 숫자로 나누어지는 가장 작은 숫자입니다. 그럼 1에서 20사이의 모든 숫자로 나누어지는 가장 작은 숫자는 몇인가? 라는 문제입니다.

 

이 문제는 두 가지 정도의 풀이 방식이 있다고 생각합니다.

 

1. 1부터 20까지의 최소공배수(LCM, Lowest Common Multile)를 구한다.

2. 문제 3번에서 보았던 산술의 기본정리 와 합성수의 성질을 이용한다.

 

1번에 대한 설명

1에서 20사이의 모든 숫자로 나누어지는 가장 작은 숫자라는 의미는, 1에서 20사이의 모든 숫자의 최소 공배수를 의미합니다. 여기서 주의할만한 최소공배수의 정의 중 하나는 다음과 같은 것이 있습니다.

 

ko.wikipedia.org/wiki/%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98

여러 개의 정수 n₁, n₂, ... n_k ∈ Z : n_k ≠ 0의 최소공배수 lcm{n₁, n₂, ..., n_k}는 "(재귀적 정의) lcm{lcm{n₁, n₂, ..., n_k-1}, n_k}"와 동치이다.

 

즉, 1에서 5까지의 최소공배수를 다음과 같이 표시할 수 있다는 뜻입니다.

・lcm{lcm{lcm{lcm{5, 4}, 3}, 2}, 1}

 

 

mathbang.net/206

그리고 최소공배수는 최대공약수를 이용하여 구할 수 있습니다.

 

두 수를 A, B, 최대공약수를 G, 최소공배수를 L이라고 하였을 때, L = (A * B) / G입니다.

 

이들을 종합하여 구현한 코드는 아래와 같습니다.

 

# n : number
n = 20

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

    return a

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

a = 1
for i in range(2, n + 1) :
    a = lcm(a, i)

print(a)

 

 

2번에 대한 설명

문제 3번에서 보았던 산술의 기본정리인 "모든 자연수는 꼭 한가지 방법으로 소수의 곱으로 표현할 수 있다" 와 합성수의 성질인 "모든 합성수는 소수들만의 곱으로 나타낼 수 있다" 이 두 가지를 이용하여 문제를 해결합니다.

 

 

2-1. 이론적 계산

1에서 20까지의 모든 숫자로 나누어지는 숫자중, 가장 간단하게 알 수 있는 숫자는 다음과 같습니다.

 

n = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19 * 20

 

먼저 중복값으로 생각할 수 있는 합성수를 제외하도록 합니다.

 

예를 들면 아래와 같습니다.

 

2, 4, 8, 16 = 2, 2^2, 2^3, 2^4

16을 제외한 나머지 합성수는 16의 약수이기 때문입니다.

 

마찬가지로 3도 제외시킵니다.

3, 9 = 3, 3^2

 

위에서 제외하지 않은 숫자(2^4, 3^2)들을 구성하고있는 숫자들의 조합 및 소수의 곱으로 만들어지는 숫자도 제외합니다.

 

6, 12, 18 = 2 * 3,   2^2 * 3,   2 * 3^2

 

10, 20 = 2 * 5,  2^2 * 5

 

14 = 2 * 7

 

15 = 3 * 5

 

이렇게 중복되는 값들을 제외하면, 남는 숫자들은 "1, 소수(5, 7, 11, 13 ,17, 19), 소수의 곱으로 이루어진 수(2^4, 3^2)"가 됩니다.

수식으로 표현하면 다음과 같습니다.

 

n = 1 * 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19

 

 

 

2-2. 코드화

위에서 적은 이론을 코드화한 것은 다음과 같습니다.

 

import math

# n : number
n = 20

# make array of prime number between 1 and n
def makePnumArr(n) :
    a = [True] * (n + 1)

    max_len = math.ceil(math.sqrt(n))

    for i in range(2, max_len) :
        if a[i] :
            for j in range(i+i, n + 1, i) :
                a[j] = False

    return [i for i in range(2, n + 1) if a[i]]


pArr = makePnumArr(n)
a = 1
for i in pArr :
    a = a * int(math.pow(i, math.floor(math.log(n) / math.log(i))))

print(a)

위의 코드에서 소수의 배승을 구하는 부분(math.pow(...))은 아래의 블로그를 참조하였습니다.

 

www.mathblog.dk/project-euler-problem-5/

Solution to Project Euler problem 5 in C# | MathBlog