Editing Euler problems/31 to 40 (section)

== [http://projecteuler.net/index.php?section=problems&id=35 Problem 35] ==
How many circular primes are there below one million?

Solution:
<haskell>
import Data.List (tails, (\\))
 
primes :: [Integer]
primes = 2 : filter ((==1) . length . primeFactors) [3,5..]
 
primeFactors :: Integer -> [Integer]
primeFactors n = factor n primes
    where
        factor _ [] = []
        factor m (p:ps) | p*p > m        = [m]
                        | m `mod` p == 0 = p : factor (m `div` p) (p:ps)
                        | otherwise      = factor m ps
 
isPrime :: Integer -> Bool
isPrime 1 = False
isPrime n = case (primeFactors n) of
                (_:_:_)   -> False
                _         -> True
 
permutations :: Integer -> [Integer]
permutations n = take l $ map (read . take l) $ tails $ take (2*l -1) $ cycle s
    where
        s = show n
        l = length s
 
circular_primes :: [Integer] -> [Integer]
circular_primes []     = []
circular_primes (x:xs)
    | all isPrime p = x :  circular_primes xs
    | otherwise     = circular_primes xs
    where
        p = permutations x
 
problem_35 :: Int
problem_35 = length $ circular_primes $ takeWhile (<1000000) primes
</haskell>

Using isPrime from above, and observing that one that can greatly reduce the search space because no circular prime can contain an even number, nor a 5, since eventually such a digit will be at the end of the number, and
hence composite, we get: (HenryLaxen 2008-02-27)

<haskell>
import Control.Monad (replicateM)

canBeCircularPrimeList = [1,3,7,9]

listToInt n = foldl (\x y -> 10*x+y) 0 n
rot n l = y ++ x where (x,y) = splitAt n l
allrots l = map (\x -> rot x l) [0..(length l)-1]
isCircular l =  all (isPrime . listToInt) $ allrots l
circular 1 = [[2],[3],[5],[7]]  -- a slightly special case
circular n = filter isCircular $ replicateM n canBeCircularPrimeList

problem_35 = length $ concatMap circular [1..6]
</haskell>