Project Euler 51

プロジェクトオイラー
http://projecteuler.net/index.php

Q51.
例えば、56○○3の○に同じ数字を入れる。このとき7つが素数になる。○はいくつでもよい。素数が8つになる最小の整数。

0〜9を○に入れたうちの8つ以上が素数なので、少なくとも素数が3つ連続することになる。よって、少し考えると、隣との差は6の倍数でなければならないことが分かる。○の個数は3の倍数でなければならない。また、1の位は○であってはならない。

from itertools import count, permutations
def is_prime(n):

    if n == 1:

        return False

    elif n == 2:

        return True

    elif (n & 1) == 0:

        return False

    

    p = 3

    while p * p <= n:

        if n % p == 0:

            return False

        p += 2

    return True
def resolve(n):

    a = [ ]

    while n:

        a.append(n % 10);

        n /= 10

    return a
def unresolve(a):

    n = 0

    for i in reversed(a):

        n = n * 10 + i

    return n
def embed(a, b, d):

    c = [ ]

    it = 0

    for e in b:

        if e:

            c.append(a[it])

            it += 1

        else:

            c.append(d)

    return c
def is_probable(a, b, min_p):

    d = 0

    if b[len(b)-1] == 0:

        d = 1

    return unresolve(embed(a, b, d)) < min_p
def get_min(a, b, min_p):

    if not is_probable(a, b, min_p):

        return 0

    

    counter = 0

    m = 0

    d_min = 0

    if b[len(b)-1] == 0:

        d_min = 1

    for d in range(9, d_min - 1, -1):

        p = unresolve(embed(a, b, d))

        if is_prime(p):

            m = p

            counter += 1

    

    if counter == N:

        return m

    else:

        return 0
def min_prime(n):

    min_p = 10 ** n

    for m in range(n - 3, 0, -3):

        pat = [ 1 ] * m + [ 0 ] * (n - m)

        for q in range(10**(m-1), 10**m):

            a = resolve(q)

            for b in permutations(pat):

                if b[0] == 0:

                    continue

                new_min_p = get_min(a, b, min_p)

                if new_min_p:

                    min_p = new_min_p

    

    if min_p < 10 ** n:

        return min_p

    else:

        return 0
N = 8

for n in count(5):

    m = min_prime(n)

    if m:

        print m

        break