Project Euler 35

問題

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

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

100万未満の巡回素数はいくつあるか?
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2035

回答

0,2,4,5,6,8は2桁以上の巡回素数の桁には含まれない。これらの数字が1桁目になると必ず2か5で割り切れるからである。
したがって、2,5以外に考察すべきは1,3,7,9だけを含む数である。
この数だけの集合を作成するために、mapallなる関数を作った。
mapallは、ある集合iter1の各要素e1,e2を適当な結合則fで指定された回数numだけ結合させ、結果をset型で返す関数である。
まず['',1,3,7,9]をiter1として、最大と考えられる6桁の数字を作ってみた。''が入っているのは、結合したときに元のリストの要素が結合後のリストにも残るようにである。たとえば''+'3'は'3'となり、元のリストの要素が結合後のリストにも残ることとなる。

import mymath
def circle(num):
  s = str(num)
  for c in range(len(s)):
    s = s[1:]+s[0]
    yield int(s)

def mapall(f, iter1, num=1):
  ret = iter1
  for i in range(num):
    ret = set([f(e1,e2) for e1 in ret for e2 in iter1])
  return ret

def connect_num(e1,e2):
  return str(e1)+str(e2)

def main():
  pri = mymath.get_primes(10**6)
  n_list = ['',1,3,7,9]
  pn5 = mapall(connect_num, n_list,5)
  pn5.remove('')
  ans = {}
  for pn in pn5:
    if pn in ans:
      continue
    flag = True
    for n in circle(pn):
      if not pri['bool'][n]:
        flag = False
        break
    if flag:
      for n in circle(pn):
        ans[n] = True
  print len(ans)+2
main()