Project Euler #5

Project Euler #5

---

• 문제
  
  • 풀이 1
  • 풀이 2
• 후기

문제

---

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 ~ 10의 최소공배수)
1부터 20까지의 모든 수로 나누어 떨어지는 가장 작은 수는 무엇인가?

풀이 1

---

• 해당 문제는 1부터 20까지의 수들에 대한 최소공배수를 구하는 문제이다.
  $$\operatorname{lcm}(1,2,\dots,19,20) = [1,2,\dots,19,20]=?$$

• 1은 제외해도 된다.(2 ~ 20까지의 수)
  $$\operatorname{lcm}(2,3,\dots,19,20) = [2,3,\dots,19,20]=?$$

• 최소공배수는 주어진 수를 소인수 분해한 결과 중 소수의 지수가 큰 수들을 곱한 값이다.
  $$a=n_{1}^{2} \times {\color{Red}n_{2}^{4}} \times {\color{Red}n_{3}} \\ b={\color{Red}n_{1}^{5}} \times n_{2}^{2} \times {\color{Red}n_{4}^{2}} \\ \operatorname{lcm}(a, b) = {\color{Red}n_{1}^{5}} \times {\color{Red}n_{2}^{4}} \times {\color{Red}n_{3}} \times {\color{Red}n_{4}^{2}}$$

• 이것들을 가지고 잘 섞어서 풀었다.

import time
num = 20
pl = [2]                            #2는 유일한 짝수인 소수
rs = []
x = 1
stime = time.time()                 #시작 시간

for i in range(3, num + 1, 2):      #1 ~ num까지의 모든 소수 계산(2를 제외한 모든 소수는 홀수다.)
    for j in range(3, i + 1, 2):
        if i % j == 0 and j != i:
            break
        elif i % j == 0 and j == i: #소수 여부를 판단.
            pl.append(i)

for k in pl:
    l = 1
    while pow(k, l) < num:          #구간내의 소수의 거듭제곱
        rs.append(k)
        x *= k                      #소수들의 곱으로 최소공배수 계산
        l += 1

print(rs, x)
print(time.time() - stime)          #수행 시간

풀이 2

---

• 이번엔 에라토스테네스의 체를 이용한다.
  

에라토스테네스의 체
- 에라토스테네스가 고안해낸 특정 수 이하의 모든 소수를 구하는 알고리즘이다.
- 여기서 특정 수는 2이상의 자연수이다.
- 구하는 순서는 아래와 같다.
1. 2에서 구하는 수($x$)까지의 정수를 순서대로 나열한다.
(다음을 만족 하는 수열로 나타낼 수 있다.
$a_{n} = n, \ \text{where} \quad x \geqq 2 \quad \text{and} \quad 2 < n \leqq x$)
2. 위 수열에서 첫번째 수를 선택한다.(2가 선택된다.)
3. 2단계에서 선택된 수(2)를 제외한 나머지 배수(4, 6, …)를 수열에서 제거한다.
4. 다시 수열에서 두번째 수를 선택한다.(2단계의 반복, 3이 선택된다.)
5. 3단계에서 선택된 수(3)를 제외한 나머지 배수(6, 9, …)를 수열에서 제거한다.(3단계의 반복)
6. 수열의 마지막까지 위의 2 ~ 5 단계를 반복한다.
7. 수열의 남은 수가 모두 소수이다.

import time
num = 20000
rs = 1
SE = [0]*(num + 1)
SE[0:2] = [1] * 2                   #0과 1은 소수가 아니다.
stime = time.time()                 #시작 시간

for idx, ck in enumerate(SE):       #에라토스테네스의 체 구현
    if ck == 0:
        SE[idx * 2::idx] = [1] * ((num // idx) - 1)

for idx, ck in enumerate(SE):
    if ck == 0:
        power = 1
        while power <= num:          #구간내의 소수의 거듭제곱
            power *= idx             #소수들의 곱으로 최소공배수 계산
        rs *= power // idx

print(rs)
print(time.time() - stime)          #수행 시간

후기

최소공배수를 활용한 부분을 제외하면 크게 어려운 부분은 없다.
앞으로도 소수에 대한 문제가 있을 때 에라토스테네스의 체가 자주 사용될 것 같다.