Project Euler #46 - 골드바흐의 다른 추론

프로젝트 오일러 46번
Goldbach's other conjecture

유명한 "골드바흐의 추론" 말고 다른 추론 - 소수가 아닌 모든 홀수는 (소수+제곱수)로 표현된다-은 틀렸다. 소수와 제곱수의 합으로 표현되지 않는 소수가 아닌 홀수 중 가장 작은 것은?

일단, 소수를 모두 찾아두고, 임의의 (소수가 아닌) 홀수에 대해 그보다 작은 제곱수들에 대한 loop을 돌면서 차이가 소수가 되는지 체크한다.

그냥.. 하면 된다 -.-;

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]]

def Gold(n,pn,sq):
    for s in sq:
        if n - 2*s in pn: return True
        if n - 2*s < 1: return False
    return False

def findNGold(MX):
    pn = set(rwh_primes1(MX))
    sq = [x*x for x in range(1,int((MX/2)**.5)+1)]
    for n in [n for n in range(9,MX,2) if n not in pn]:
        if Gold(n,pn,sq) == False:
            return n

print findNGold(10000)

이 추론이 어디서 깨질 지 몰라서 10만까지 체크해 봤다. 그러면 0.02초
10000까지만 체크하면 0.005초