Project Euler 132

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

この問題は、素直に10のべき乗の素数による剰余を計算すればよいでしょう。

from itertools import *

def gen_primes():
    a = [ True ] * L
    for p in (n for n in xrange(2, L) if a[n]):
        for k in xrange(p * 2, L, p):
            a[k] = False
    primes = [ n for n in xrange(2, L) if a[n] ]
    for p in primes:
        yield p
    
    for m in count(1):
        start = m * L
        end = start + L
        a = [ True ] * L
        for p in takewhile(lambda p: p * p < end, primes):
            k0 = (start + p - 1) / p * p - start
            for k in xrange(k0, L, p):
                a[k] = False
        
        for p in (start + k for k in xrange(L) if a[k]):
            primes.append(p)
            yield p

N = 10 ** 9
L = 10000
M = 40
g = ifilter(lambda p: p % 3 != 0 and pow(10, N, p) == 1, gen_primes())
print sum(islice(g, M))