Project Euler #7 - 10001번째 소수 찾기

제목 그대로 10001번째 소수 찾기

가장 빠른 방법 - 충분한 수의 소수를 미리 만들어 두고, 10001번째를 찾는다.  N이 충분히 클 때 N 보다 작은 소수가 대략 몇 개나 될 지에 대한 공식이 있으나.. 대략 20만 정도면 충분할테니 굳이 그 공식을 가져올 필요는 없다. 0.01초 걸린다. (rwh_primes1에 대해서는 소수 만들기 글 )

def rwh_primes1(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * (n/2)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]:
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

pn = rwh_primes1(200000)
print pn[10000]

마지막 소수에서 다음 소수를 찾는 방식으로 하면 20배쯤 오래 걸린다.

def chk_pn(n,pn):
    for p in pn:
        if n % p == 0: return False
        if p**2 > n: return True

def inc_pn(pn):
    n = pn[-1] + 2
    while True:
        if chk_pn(n,pn): pn.append(n); return pn
        n += 2

pn = [2,3]
for i in range(9999):
    pn = inc_pn(pn)

print pn[-1]

계산시간의 차이는 없으나 이 코드가 좀 나은 것 같아서...

def isprime(n, primes):
    for p in primes:
        if n % p == 0: return False
        if p*p > n: return True

primes = [2]
n, cnt = 3, 1
while cnt < 10001:
    if isprime(n,primes):
        primes.append(n)
        cnt += 1
    n += 2

print primes[-1]

===

구글에서 "10001번째 소수"로 검색해서 나온 결과들을 쭉 읽어봤다. c나 java코드를 내가 잘못 해석한 부분이 있을 수는 있으나.. 다들 좀 아쉬움이 남는 코드들이다. 누군가 내 코드를 봐도 그렇겠지..

일단, prime sieve를 제대로 구현한 코드가 없다. 이건 나도 가져다 쓴 거니 할 말은 없지만서도..
하나씩 찾는 방법에서, n을 2씩 증가시키고, p*p > n이면 더 이상 체크하지 않고, 무엇보다 "이전에 찾았던 소수로만 나눠보면 된다"는 게 반영된 코드는 없었다. 슬픈 현실인가? 나한테는 또다른 기회인가?