Project Euler Problem 035

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

197は巡回素数と呼ばれる. 桁を回転させたときに得られる数 197, 971, 719 が全て素数だからである.

100未満には巡回素数が13個ある: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, および97である. 100万未満の巡回素数は何個か?

ある素数が巡回素数であるか?を調べるので、

  • 100万未満の素数を列挙する
  • 素数について、巡回させても素数となるかを一巡回するまで調べる

もうちょっとやりかたがありそう。

import math
import datetime


def primelist(limit=1000):
    checked = [ True ] * ((limit-1)/2)
    result = [2]
    for i in xrange(len(checked)):
        val = i * 2 + 3
        if checked[i]:
            result.append(val)
            j = val + val + val
            while j < limit:
                checked[(j - 3) / 2] = False
                j += val + val
    return result


def nlen(n):
    if n <  0: return 0
    if n == 1: return 1
    return int(math.ceil(math.log(n) / math.log(10)))



def is_circular_prime(n, primes):
    
    sentinel = x = n
    l = math.pow(10, nlen(n)-1)
    
    while True:
        if x not in primes:
            return False
        
        x = int(x / 10 + (x % 10) * l)
        
        if x == sentinel:
            return True


def euler035():
    N = 1000000
    l = set(primelist(N))
    
    result = 0
    for i in l:
        if is_circular_prime(i, l):
            result += 1
            
    print result        


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

答え: 55
実行時間: 0.864688秒くらい