Project Euler 111

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

単純に、対象となる整数を生成して素数判定します。生成は、例えば4桁で1を3つ使うとすると、残りの1つの桁をまず決めて、そこに1以外の数字をあてはめます。素数判定は、単純に素数で割っていきます。
これで2秒でした。もうちょっとなんとかならないでしょうか。
素数性を調べる対象は、大半は最後の桁が繰り返しの数字ではない場合です。そのため10個がまとまっているので、エラトステネスのふるいが使えそうです。ただ、やってみると桁数が大きくなるにつれて遅くなりました。
単純にミラー・ラビン素数判定法を使ったら0.3秒でした。
以下は、それを使っていないコードです。

from itertools import *
import time

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 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 S(d):
    def gen_0(m):
        for a in combinations(range(1, N), m - 1):
            yield (0,) + a
    
    def gen_number(m):
        if d == 0:
            g = gen_0(m)
        else:
            g = combinations(range(N), m)
        for a in g:
            for b in product(range(d) + range(d + 1, 10),
                                            repeat = len(a)):
                if b[0] == 0 and a[0] == 0:
                    continue
                c = [ d ] * N
                for x, y in izip(a, b):
                    c[x] = y
                yield to_number(c)
    
    def S_(m):
        return sum(filter(is_prime, gen_number(m)))
    
    return ifilter(lambda s: s > 0, imap(S_, count(1))).next()

t = time.clock()
N = 10
primes = sieve(int(10 ** (N / 2.) + 1))
print sum(S(d) for d in range(10))
print time.clock() - t