Project Euler Problem 037

http://projecteuler.net/index.php?section=problems&id=37
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2037

3797は面白い性質を持っている. 
まずそれ自身が素数であり, 左から右に桁を除いたときに
全て素数になっている (3797, 797, 97, 7). 
同様に右から左に桁を除いたときも全て素数である (3797, 379, 37, 3).

右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ.

注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.

右から左に切り詰めたとき、最終的に最上位桁の数が残る。この数が素数でないといけないので、最上位桁は一桁の素数 2,3,5,7 のいずれかである事がわかる。
同じように、左から右に切り詰めてたとき、最終的に最下位桁の数が残る。右から左に切り詰める時と同じように最下位桁も素数でないといけないが、2 は切り詰める過程で偶数を作り出すので 2 をのぞいた 3,5,7 のいずれかである事がわかる。
間の数は左から右に切りつめる過程で最下位桁になるので奇数でないといけない。

上記の条件に当てはまる数だけを調査し、11個発見した時点で終了する。

import math
import itertools
import datetime


def is_prime(n):
    if n < 2: return False
    if n < 4: return True
    if n % 2 == 0: return False
    if n < 9: return True
    if n % 3 == 0: return False

    r = math.floor(math.sqrt(n))
    f = 5
    while f <= r:
        if n % f == 0: return False
        if n % (f+2) == 0: return False
        f += 6
    return True


def nlen(n):
    return int(math.ceil(math.log(n)/math.log(10)))


def is_interesting_property(n):
    m = n / 10
    while m:
        if not is_prime(m):
            return False
        m /= 10
    
    l = int(math.pow(10, nlen(n)-1))
    while l > 1:
        if not is_prime(n % l):
            return False
        l /= 10
    
    return True


def candidates(length):
    midlen = length - 2
    
    expa = int(math.pow(10, length-1))
    
    for a in [2,3,5,7]:
        vala = a * expa
        
        if midlen == 0:
            for valc in[3,5,7]:
                yield vala + valc
        else:
            for b in itertools.product([1,3,5,7,9], repeat=midlen):
                valb = reduce(lambda a, b: a * 10 + b, b) * 10
                for valc in [3,5,7]:
                    yield vala + valb + valc


def euler037():
    v = 0
    c = 0
    for i in itertools.count(2):
        for j in candidates(i):
            if not is_prime(j): continue
            
            if is_interesting_property(j):
                v += j
                c += 1
                print '', j
                if c == 11: break
        else: continue
        break
        
    print v
    

                    
begin = datetime.datetime.now()
euler037()
end = datetime.datetime.now()
print end - begin

答え: 748317
実行時間: 0.090463秒くらい