Project Euler #7

Project Euler #7

---

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

문제

---

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10001st prime number?

처음 6개의 소수는 2, 3, 5, 7, 11, 13이며 6번째 소수가 13임을 알 수 있다.
10001번째 소수는 무엇인가?

풀이 1

---

• Project Euler #3에서 합성수를 다음과 같이 표현했다.
  $$n =\sqrt{n} \cdot \sqrt{n}= a\cdot b \; , \text{where} \quad 1 < a \text{ OR } b \leqq \sqrt{n}$$
• 즉, $1 < a \leqq \sqrt{n}$를 만족하는 $a$가 있으면 해당 수는 합성수이다.
• 또한, $a$가 합성수이면 위와 상관없이 $n$도 합성수이므로 소수에 대해서만 검증하면 된다.
• 따라서, 자연수 $n$에 대하여 $1 < a \leqq \sqrt{n}$를 만족하는 소수$a$가 존재하지 않으면 $n$은 소수다.

num = 10001
pl = [2]
i = 1
stime = time.time()

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

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

풀이 2

---

• 에라토스테네스의 체를 이용하여 풀 수 있다.

import time
num = 10001
cnt = 0
SE = [0]*(10000000 + 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] * ((10000000 // idx) - 1)
        cnt += 1
    if cnt == num:
        idx
        break

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

후기

문제 중에 소수와 관련된 문제가 적지 않다.
Project Euler #5의 에라토스테네스의 체가 다시 사용되었다.