Project Euler 118

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

Q118.
1〜9のすべての数字を使って、いくつかの自然数を作る。{2,5,47,89,631}のように、その全てが素数である組合せは何通りあるか。

1〜9の順列を発生させる。最後が4,6,8は不可。重複しないように、例えば{4,5,2,9,8,1,6,3,7}だったら、左から自然数を作るときに、最初は1を含むようにする。452981,4529816,4529813となる。よって、最後が1でも不可。452981が素数なら、残った数字で最小のものを含むようにする。すなわち、63,637になる。このようにして最後まで素数ならカウントする、というのを再帰的に処理する。

from itertools import permutations, imap
def make_primes(limit):

    for n in xrange(3, limit + 1, 2):

        if is_prime(n):

            primes.append(n)

    return primes
def is_prime(n):

    if n < 2:

        return False

    for p in primes:

        if p * p > n:

            return True

        elif n % p == 0:

            return False

    return True
def decode(a):

    n = 0

    for e in a:

        n = n * 10 + e

    return n
def find_min_pos(a):

    min_d = 10

    min_pos = 0

    for i in range(len(a)):

        if a[i] < min_d:

            min_d = a[i]

            min_pos = i

    return min_pos
def count_prime_sets(a):

    if a[-1] == 1 or a[-1] == 4 or a[-1] == 6 or a[-1] == 8:

        return 0

    

    s = 0

    if is_prime(decode(a)):

        s = 1

    for pos in range(find_min_pos(a) + 1, len(a)):

        if is_prime(decode(a[:pos])):

            s += count_prime_sets(a[pos:])

    return s
primes = [ 2 ]

make_primes(int(10 ** 4))

print sum(imap(count_prime_sets, permutations(range(1, 10))))