프로젝트 오일러 7번 문제

10001st prime

Problem 7

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 10 001st prime number?

문제는 심플하다. 6번째 소수는 13이다. 그렇다면 10001번째 소수는 뭘까?

역시 프로젝트 오일러의 문제는 쉬운듯 하면서도 생각을 한번 더 하게 되는게 매력이다.

일단 가장먼저 생각나는 것은 얼마전에 문제 풀다가 뻘짓하면서 배워둔 에라토스테네스의 체다. 

https://shiningstone.tistory.com/2

혼자 뻘짓하면서 애를 먹었던 3번 문제에서 공부했었다. 문제와 상관없는 내용이었지만 배운 점은 있다.

바로 문제 분석의 중요성과 에라토스테네스의 체 개념이다.

그럼 이 문제를 분석해보자. 10001번째 소수를 구하라한다. 

그럼 여기서 드는 생각이 있다. 에라토스테네스는 10001번째 수가 소수인지를 빠르게 판단해낼 수 있지만 

과연 10001번째 소수를 구하는데에도 소수를 구하는 알고리즘보다 빠를까? 체를 만들고, 세는 과정이 필요하기 때문이다.

내가 말한 소수를 구하는 알고리즘은 하나씩 확인하는 방법을 탐색하지 않아도 되는 경우들을 제외해 최적화한 알고리즘을 말한다.

ex ) N의 제곱근까지 탐색, 홀수만 탐색

비교를 위해 둘다 만들어보기로 했다. 

우선 체를 이용한 코드.

from time import time


def eratos(num):
    sieve = [False, False] + [True] * num
    count = 0
    for i, val in enumerate(sieve):
        if val:
            count +=1
            sieve[i*2::i] = [False] * len(sieve[i*2::i])
            if(count == 10001):
                print(i)
                break

    return [i for i,x in enumerate(sieve) if x]


start_t = time()

li = eratos(150000)

print(time() - start_t)

소수를 찾을 때마다 count+1 시키고 count가 10001이 되는 순간 break로 빠져나오기 때문에 생각했던 문제는 없었다.

정답을 찾아내는데 걸린 시간은 0.03~0.04초. 예상했던 문제가 없었기 때문에 소수 구하는 알고리즘보다 빠를 것같다.

이미 결과는 예상할 수 있지만 위에서 든 의문에 대한 비교를 위해 소수를 구하는 알고리즘을 이용한 코드도 짜봤다.

from time import time


def is_prime(n):
    if n<2:
        return False
    if n in [2,3]:
        return True
    if n % 2 is 0 or n % 3 is 0:
        return False
    if n < 9:
        return True
    k, l = 5, n**0.5

    while k <= l:
        if n % k is 0 or n % (k+2) is 0:
            return False
        k += 6
    return True



start_t = time()

count = 0
for i in range(150000):
    if(is_prime(i)):
        count += 1
        if count == 10001:
            print(i)
            break

print(time() - start_t)

사용된 최적화 기법 : 2보다 작으면 False, 2,3이면 True , 9미만 이고 2 3으로 나누어 떨어지지 않으면 True 떨어지면 False, 제곱근 까지만 탐색

자세한 출처.

https://53perc.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%86%8C%EC%88%98-%ED%8C%90%EB%B3%84%ED%95%98%EA%B8%B0

답을 도출하는데 걸린 시간은 0.24초가량. 꽤 빠른 속도지만 에라토스 체에는 한참 못미친다.

게시판에 있는 깔끔한 코드를 하나 가져왔다.

import math

target = 200000
sieve = [True for _ in range(0, target + 1)]
sieve[0] = False
sieve[1] = False

# sieve of eratosthenes, using a list of boolean values
# index of list is the actual numbers to be tested
for i in range(2, int(math.sqrt(target))+1):
    if sieve[i]:
        for j in range(2, (target // i) + 1):
            sieve[i*j] = False

primes = [x for x in range(2, len(sieve)) if sieve[x]]

# print the 10001st prime (10000 since list starts at 0)
print(primes[10000])

sieve 초기화 방식이 다르고 리스트 슬라이싱을 사용하진 않았지만 제곱근을 이용해 속도를 최적화 시켰다.

내 코드에도 제곱근 방식을 적용해보았다.

from time import time
import math


def eratos(num):
    sieve = [False, False] + [True] * num
    
    for i in range(2, int(math.sqrt(num))+1):
        if sieve[i]:
            sieve[i*2::i] = [False] * len(sieve[i*2::i])


    return [i for i,x in enumerate(sieve) if x]


start_t = time()

li = eratos(200000)

print(li[10000])

print(time() - start_t)

걸린 시간은 0.3~0.4초로 시간의 단축을 느낄 수 없었다. 그래서 1만이 아닌 100만 1 번째 소수를 구해봤다.

비교를 해보자면 math.sqrt를 사용하는 경우에는 if문을 이용한 탈출이 없지만 num 자체가 작고,

제곱근을 사용하지 않는 경우에는 if문을 사용하여 원하는 때에 탈출할 수 있다.

from time import time
import math


def eratos(num):
    start_t = time()
    sieve = [False, False] + [True] * num
    
    for i in range(2, num):
        if sieve[i]:
            sieve[i*2::i] = [False] * len(sieve[i*2::i])
            if num == 1000001:
                break

        

    print(time() - start_t)

    start_t = time()
    return [i for i,x in enumerate(sieve) if x], start_t




li, start_t = eratos(55555555)



print(li[1000000])

print(time() - start_t)

먼저 math.sqrt 를 사용하지 않는경우.

return 전까지 걸린시간은 무려 17초. return은 4초이상 걸린다.

from time import time
import math


def eratos(num):
    start_t = time()
    sieve = [False, False] + [True] * num
    
    for i in range(2, int(math.sqrt(num))+1):
        if sieve[i]:
            sieve[i*2::i] = [False] * len(sieve[i*2::i])
   
    print(time() - start_t)

    start_t = time()
    return [i for i,x in enumerate(sieve) if x], start_t




li, start_t = eratos(55555555)



print(li[1000000])

print(time() - start_t)

그리고 제곱근을 사용한 경우의 시간은 return문 전까지 7.3초. 무려 두배 이상 빠른 속도다.

이는 55555555라는 매우 큰수를 사용했음에도 이 수의 제곱근은 7453.5 ... 정도 밖에 되지 않기 때문이다.

최종 완성된 코드

#from time import time
import math


def eratos(num):
    #start_t = time()
    sieve = [False, False] + [True] * num
    
    for i in range(2, int(math.sqrt(num))+1):
        if sieve[i]:
            sieve[i*2::i] = [False] * len(sieve[i*2::i])

    #print(time() - start_t)

    #start_t = time()
    return [i for i,x in enumerate(sieve) if x]#, start_t




#li, start_t = eratos(55555555)

li = eratos(200000)


print(li[10000])

#print(time() - start_t)