http://odz.sakura.ne.jp/projecteuler/index.php?Problem%2035
以下の事実を利用する。
・巡回素数の条件を満たす数は、1,3,7,9の組み合わせとなる。
※偶数、もしくは5が一桁にあった場合、2または、5で割り切れるため。
方針
1,3,7,9の6桁の組み合わせをもれなく作成し、巡回素数かどうかを判定する。
この組み合わせを作成するために、0を加えた5進数を利用する。5進数のそれぞれの桁の1,2,3,4が、10進数の1,3,7,9に対応するようにすれば、組み合わせをもれなく作成でき、なおかつ計算量を減らすことができる。
なお、エラトステネスのふるいや、途中で出てきた巡回素数を記憶等を用いれば計算量をさらに減らすことができるが、今回は実装しなかった。
#! /usr/bin/env python
# -*- coding: utf-8 -*-
#
prims = [ 0, 1, 3, 7, 9]
def is_prim(p):
j = 2
while j * j<=p:
if not p % j :
return 0
j+=1
return 1
def get_turn_num(n):
if n < 10:
return n
else:
return int("%s%s" % ((n %10) , (n//10)))
def is_turn_prim(p,n=0):
if not is_prim(p):
return 0
n = get_turn_num(p)
while p != n :
if not is_prim(n):
return 0
n = get_turn_num(n)
return 1
def get_num(i):
j = 0
num=0
while i :
num += prims[i % len(prims)] *( 10 ** j )
i //= len(prims)
j+=1
return num
nums = []
i=2
max = len(prims) ** 6
while i < max:
#print i
target = get_num(i)
if is_turn_prim(target):
nums.append(target)
i+=1
print len(nums) + 2
実行結果
real 0m0.888s
user 0m0.817s
sys 0m0.007s