Project Euler #58 - spiral primes

프로젝트 오일러 58번 - 나선형 숫자 배열에서의 소수
5  4  3
6  1  2
7  8  9...
처럼 1부터 나선형으로 숫자를 하나씩 늘려갈 때 대각선에 있는 숫자 중 소수의 비율이 10% 이하가 될 때, 한 변의 길이는?
문제의 예시를 보면, 변의 길이가 7일 때 소수의 비율은 62% 정도이다. 10% 이하로 떨어지려면 꽤 큰 수가 필요할 듯 하다.

변의 길이가 늘어날 때마다 1. 대각선에 추가되는 숫자 네 개가 어떤 것인지 공식을 만들고, 2. 그 숫자들이 소수인지 체크하고, 3. 그 때마다 소수 비율이 10% 이하로 떨어지는지 체크한다.
1. 28번과 같은 문제이다. 오른쪽 아래로 1, 9, 25, 49, ... 패턴을 보이는 데에서 시작하면 된다.
2. 100억을 넘지 않는다고 가정했을 때, a. 100억까지의 모든 소수를 찾아둔다. b. 10만까지의 소수를 찾아두고 이를 이용해서 소수인지 체크한다. 중 b가 메모리 사용이나 속도면에서 더 낫다.
3. 그냥 세면 된다.

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 chk_pn(n,pn):
    for p in pn:
        if n % p == 0: return False
        if p ** 2 > n: return True

chk_N = 100000
pn = rwh_primes1(chk_N)

nprimes = 0
for slen in range(3,chk_N,2):
    if chk_pn(slen*slen - (slen-1),pn): nprimes += 1
    if chk_pn(slen*slen - (slen-1)*2,pn): nprimes += 1
    if chk_pn(slen*slen - (slen-1)*3,pn): nprimes += 1
    if nprimes / (slen*2-1.0) < .1:
        print slen
        break

1.8초. 꽤 큰 숫자까지 체크하는 거니까 이정도로 만족