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