Project Euler #10

Project Euler #10

---

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

문제

---

The sum of the primes below 10 is $2 + 3 + 5 + 7 = 17$.
Find the sum of all the primes below two million.

10 이하 소수의 합은 $2 + 3 + 5 + 7 = 17$이다.
200만 이하 소수의 합을 구하라.

풀이 1

---

• 다시 한번 합성수의 성질을 이용했다.
  $$n =\sqrt{n} \cdot \sqrt{n}= a\cdot b \; , \text{where} \quad 1 < a \text{ OR } b \leqq \sqrt{n}$$
• 자연수 $n$에 대하여 $1 < a \leqq \sqrt{n}$를 만족하는 소수$a$가 존재하지 않으면 $n$은 소수다.
• 이제 while로 루핑을 돌린다.(노가다)
• 수행시간은 약 26초다.(느리다)

import time
num = 2000000
pl = [2]
i = 3
stime = time.time()

while i <= num:
    for j in pl:
        if j > i**0.5:
            pl.append(i)
            break
        elif i % j == 0:
            break
    i += 2

sum(pl)
print("Running Time: %f" %(time.time() - stime))

풀이 2

---

• 풀이 1이 앞서 본 것과 같이 느리다.
• 이번에도 에라토스테네스의 체를 이용한다.
• 수행시간은 약 0.7초다.

import time
num = 2000000
SE = [0] * (num + 1)
SE[0:2] = [1] * 2
rs = 0
stime = time.time()

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

print(rs)
#Run time
print("Running Time: %f" %(time.time() - stime))

풀이 3

---

• **풀이 1은 느리다. 풀이 2**는 좀 더 빠르다.
• 하지만 왠지 더 빨라질 수 있을 것 같다.
• 수행 횟수를 줄이기 위해 홀수만 수행했다.
• 수행시간은 약 0.470586초다.
• 빨라진것은 맞지만 풀이에 오류가 있다.

import time
num = 2000000
se = [0] * (num + 1)
SE = se[1::2]
SE[0] = 1
rs = 2
stime = time.time()

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

print(rs)
#Run time
print("Running Time: %f" %(time.time() - stime))

후기

이 문제에서도 에라토스테네스의 체를 구현하는 해결했다.
물론 에라토스테네스의 체가 최선이 아닐 수 있다.
좀 더 새로운 방법이 있다면 추후에 추가하겠다.