Project Euler #35 - 순환(?)소수

프로젝트 오일러 35번 - circular primes
197은 한 칸씩 옆으로 이동해도 - 즉 971, 719도 모두 소수이다. 100만 이하에서 이런 성질을 갖는 소수는 모두 몇 개인가?

1. 100만 이하의 소수를 모두 찾고,
2. 한칸씩 옮겨가며 모두 소수인지 체크하면 된다.

1은 늘 사용하던 rwh_primes1을 사용하고,
2를 실행하기 전 모든 자리가 홀수인지 체크한다. 23은 소수지만 32는 절대 소수가 될 수 없으므로.

100만 이하 소수는 78498개, 홀수로만 된 소수는 3217개

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(1000000)

pc = set()
for p in pn:
    chk = 1
    for c in str(p):
        if c in '24680':
            chk = 0
            break
    if chk == 1: pc.add(p)

#pc = {p for p in pn if {s for s in str(p)} <= set('13579')}

cnt = 1 # "2"
for p in pc:
    ps = str(p)
    chk = 1
    for i in range(len(ps)):
        if int(ps[i:]+ps[:i]) not in pc:
            chk = 0
            break
    if chk == 1: cnt += 1

print cnt

실행시간은 약 0.12초. pn 까지 0.05초, pc를 만드는 데 0.05초가 더 걸렸다. 주석으로 막아둔 부분처럼 pc를 찾는 게 코드를 알아보기 더 쉬운데 이렇게 하면 0.1초가 더 걸린다. 실행시간을 줄이려면 코드를 길게 짜야 하나보다.

덧, 197이 위의 조건을 만족하는 것을 확인했으면 971, 791에 대해서 반복해서 확인할 필요가 없다. 그런데 실행 시간 대부분은 pn과 pc를 찾는 것이다보니 그런 부분을 최적화하더라도 효과는 미미할 듯 하다.