Problem35

30分プログラム、その308。Problem35 - Project Euler。

197は巡回素数と呼ばれる. 桁を回転させたときに得られる数 197, 971, 719 が全て素数だからである.
100未満には巡回素数が13個ある: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, および97である. 100万未満の巡回素数は何個か?

力技で解いてみた。遅っ。なんか素敵な解法があるのかしら。

使い方

$ python problem35.py
...
933199
939193
939391
993319
999331
55
python problem35.py  175.48s user 1.21s system 87% cpu 3:22.29 total

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-
#
# problem35.py -
#
# Copyright(C) 2008 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2008/05/19 22:15:42
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#
import math

def shift(x):
    w = 10**int(math.log10(x))
    return w*(x%10)+x/10

def is_prime(x):
    for n in xrange(2,int(math.sqrt(x)+1)):
        if x % n == 0:
            return False
    return True

def rotate(n):
    xs = [n]
    x = shift(n)
    while not x in xs:
        xs.append(x)
        x = shift(x)
    return xs
    
def is_rot_prime(x):
    return all(map(is_prime,rotate(x)))

def main():
    n = 0
    for x in xrange(2,1000000):
        if is_rot_prime(x):
            n += 1
            print x
    print n

main()

参考

• 過去の30分プログラム
• Problem 35 - PukiWiki