Project Euler 133

プロジェクトオイラー
http://projecteuler.net/index.php

Q133.
1がk個続く整数をR(k)と表す。R(10ⁿ)の形の因数になりえない100万未満の素数の総和。

これはひっかけだ。最初「なりうる」だと思った。
素数pについて、kを2から見ていき、最初に2と5の因数しかない数がpで割り切れるか、そうでない数が割り切れるかで判定できる。

from itertools import imap, takewhile, count
def gen_primes():

    yield 2

    yield 3

    n = 3

    while True:

        n += 2

        p = 3

        while True:

            if p * p > n:

                yield n

                break

            if n % p == 0:

                break

            p += 2
def is_div_by_10pow(n):

    while (n & 1) == 0:

        n >>= 1

    while n % 5 == 0:

        n /= 5

    return n == 1
def is_10pow(p):

    if p <= 5:

        return p

    

    x = 10

    for n in count(2):

        x = x * 10 % p

        if x == 1:

            if is_div_by_10pow(n):

                print p

                return 0

            else:

                return p
N = 10 ** 5

print sum(imap(is_10pow, takewhile(lambda p: p < N, gen_primes())))