Project Euler 35（1）

Problem 35
197は、数字を回転させた197と971と719がすべて素数なので、circular primeと呼ばれる。
（中略）100万未満にcircular primeはいくつあるか？
http://projecteuler.net/index.php?section=problems&id=35

エラトステネスのふるいを行って、2から100万の1つ前まで題意どおりに行えばいいでしょう。回転は、

197 / 100 + 197 % 100 * 10 = 971

などとします。
しかし、例えば161は116が明らかに2で割り切れます。だから、偶数の数字は使えません（1桁の数以外）。5も同様です。これでチェックする数がグッと減ります。
しかし、197、971、719は、同じチェックを3回やっていることになります。これを防ぐにはどうしたらいいでしょう。

def make_primes(max_p):

    a = [ True ] * (max_p + 1)

    for n in xrange(4, max_p + 1, 2):

        a[n] = False

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

        if a[n]:

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

                a[n] = False

    return a
def is_prime(n):

    return primes[n]
def next(n, m):

    return n / m + n % m * 10
def gen_cycle(n):

    m = 10

    num_digits = 1

    while m < n:

        m *= 10

        num_digits += 1

    m /= 10

    

    yield n

    for k in range(num_digits - 1):

        n = next(n, m)

        yield n
def is_circular_prime(n):

    for m in gen_cycle(n):

        if not is_prime(m):

            return False

    return True
N = 10 ** 6

primes = make_primes(N - 1)

cprimes = filter(is_circular_prime, xrange(2, N))

print len(cprimes)

# 他の関数は上と同じ

def gen_numbers():

    yield 2

    yield 5

    for k in range(1, M + 1):

        for digits in product( (1, 3, 7, 9), repeat = k):

            yield reduce(lambda x, y: x * 10 + y, digits)
M = 6

N = 10 ** M

primes = make_primes(N - 1)

cprimes = filter(is_circular_prime, gen_numbers())

print len(cprimes)