Project Euler 118

http://projecteuler.net/index.php?section=problems&id=118


これも再帰に持ち込めます。[1,2,3,4,5,6,7,8,9]を用意して、ここから数字をいくつか取り出します。重複を避けるために最も左の数字は必ず選びます。例えば1と3を選んだとき、13も31素数なので、2つです。[2,4,5,6,7,8,9]で同じように計算し、その結果に2をかけます。
このように計算して72秒でしたが、いくつか高速化を施して25秒になりました。

from itertools import *

def sieve(max_n):
    a = [ True ] * (max_n + 1)
    for p in (n for n in xrange(2, max_n + 1) if a[n]):
        for k in xrange(p * 2, max_n + 1, p):
            a[k] = False
    return [ n for n in xrange(2, max_n + 1) if a[n] ]

def is_prime(n):
    return n >= 2 and all(n % p != 0 for p in
                takewhile(lambda p: p * p <= n, primes))

def to_number(a):
    return reduce(lambda x, y: x * 10 + y, a)

def gen_part(a, k = 0):
    if k == len(a):
        yield (), ()
    else:
        for b, c in gen_part(a, k + 1):
            yield a[k:k+1] + b , c
            yield b, a[k:k+1] + c

def gen_partitions(a, head):
    for b, c in gen_part(a[1:]):
        if not head or len(c) != 0:
            yield a[:1] + b, c

def num_primes(a):
    return sum(imap(is_prime, imap(to_number, permutations(a))))

def sum_primes_set(a, head = True):
    def mul(b, c):
        if len(b) <= len(c):
            n = num_primes(b)
            return n * sum_primes_set(c, False) if n > 0 else 0
        else:
            n = sum_primes_set(c, False)
            return num_primes(b) * n if n > 0 else 0
    
    if len(a) == 0:
        return 1
    
    return sum(mul(b, c) for b, c in gen_partitions(a, head))

primes = sieve(10000)
print sum_primes_set(tuple(range(1, 10)))