Project Euler #51 - prime digit replacements

프로젝트 오일러 51번 - 숫자를 바꿔도 소수가 되는 것
56**3은 세번째, 네번째 자리를 00, 11, 33, 44, 66, 77, 99로 바꾸어서 7개의 소수를 만들 수 있다.
적당히 바꿔서 8개의 소수를 만들 수 있는 패턴은? 이 때 가장 작은 소수는?

1자리를 바꾼다 => (A. 바꾸는 자리를 빼고 나머지 자리들의 숫자의 합) + (B. 바꾸는 자리의 수) 에서 A는 고정이고, B는 4번은 3의 배수, 3번은 3의 배수 더하기 1, 3번은 3의 배수 더하기2 => 8개의 소수를 만들 수 없다.
같은 이유로, 2자리, 4자리, 5자리를 바꾸어서는 8개의 소수를 만들 수 없다.
6자리를 바꾸는 건 나중에 생각해 보기로 하고, 일단 3자리 바꾸는 걸 시도해 보자.

고정된 자리수를 3개라고 해 보자. 문제에서 예시로 든 7개 소수 만드는 데에 만, 천, 일의 자리-세 개를 고정했었으니 아무래도 이번에도 3개나 4개가 필요할 듯 하다. 우선 3개로 시도.

또하나, 1의 자리는 1, 3, 7, 9만 올 수 있다.

i, j 자리는 0~9에서 움직일 수 있고, 1의 자리(10**0의 자리)는 1, 3, 7, 9가 움직일 수 있다고 하자. 대략 400개의 경우에 대해, 나머지 3자리를 바꾸어가면서 소수인지 체크한다.

코드 - 대략 0.06초

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 prob51(pns):
    for i in range(1,5):
        for d_i in range(0,10**(i+1),10**i):
            for j in range(i+1,6):
                for d_j in range(0,10**(j+1),10**j):
                    for k in [1,3,7,9]:
                        y = d_i+d_j+k
                        if y % 3 != 0:
                            x = sum([10**e for e in {1,2,3,4,5} - {i,j}])
                            failcnt = 0
                            for z in range(10):
                                if y + x * z not in pns: failcnt += 1
                                if failcnt == 3: break
                            if failcnt < 3:
                                if y in pns:
                                    if y > x: return y
                                elif y + x in pns: return y + x
                                else: return y + 2*x

print prob51(set(rwh_primes1(1000000)))

y 를 만들어 내는 함수를 밖으로 빼서 indent가 지저분해 지지 않도록 개선할 수 있을 듯 하지만.. 내가 이해하기에는 이게 더 편하다~