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万未満の巡回素数は何個か?
もうちょっとやりかたがありそう。
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秒くらい