Problem 35

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

なんか、素数判定に時間かかったようなきがする。

import Control.Arrow
import Data.List
rots n =map read[m|m<-take(length.show$n).iterate rot$show n]
where rot (x:xs) = xs++[x]
sieve (_,((p:ps),qs)) = (ps',(ps++ps',filter ((/=).(`mod` p)) qs'))
where (ps',qs') = span (<p*p) qs
primes = iterate sieve([2],([3],[3,5..]))>>=fst
primeFactors n = factor n primes
where
factor _ [] = []
factor m (p:ps) | p*p > m        = [m]
| m `mod` p ==  = p : factor (m `div` p) (p:ps)
| otherwise      = factor m ps
isPrime 1 = False
isPrime n = case (primeFactors n) of
(_:_:_)   -> False
_         -> True
circular [] = []
circular (p:ps)
| intersect (show p) "024568"==[] &&all isPrime (sort.tail.nub.rots$p)
= p:(circular ps)
| otherwise = circular ps
p035 = print.(+2).length. circular.takeWhile(<1000000)$ primes
More Reading
Newer// Problem 53
Older// Problem 36