# Project Euler Problem 35 Solution

## Question

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 Data.List (union)

pairwise :: (a -> a -> a) -> [a] -> [a]
pairwise f (xs:ys:t) = f xs ys : pairwise f t
pairwise _ t = t

primes :: [Integer]
primes = 2 : _Y ((3 :) . gaps 5 . _U . map (\p-> [p*p, p*p+2*p..]))
where
_Y g = g (_Y g)                      -- recursion, Y combinator
_U ((x:xs):t) = x : (union xs . _U . pairwise union) t   -- ~= nub.sort.concat
gaps k s@(x:xs)
| k < x     = k : gaps (k+2) s    -- ~= [k,k+2..]\\s, when
| otherwise =     gaps (k+2) xs   --  k <= head s && null(s\\[k,k+2..])

rotate :: [a] -> [a]
rotate [] = []
rotate (x:xs) = xs ++ [x]

rotations :: [a] -> [[a]]
rotations x = take n (iterate rotate x)
where n = length x

intRotations :: Integer -> [Integer]
intRotations = map read . rotations . show

prime :: Integer -> Bool
prime n = n > 1 && foldr (\p r -> p*p > n || ((n rem p) /= 0 && r)) True primes

circular :: Integer -> Bool
circular = all prime . intRotations

candidate :: Integer -> Bool
candidate n | n < 10 = True
| otherwise = all (elem "1379") (show n)

main :: IO ()
main = print $length . filter circular$ filter candidate $takeWhile (< 1000000) primes $ ghc -O2 -o circular-primes circular-primes.hs
$time ./circular-primes real 0m0.149s user 0m0.128s sys 0m0.020s ## Ruby #!/usr/bin/env ruby require 'mathn' puts (1..1000000).select { |i| (1..i.to_s.length).all? { |j| i.to_s.split('').rotate(j).join('').to_i.prime? } }.count $ time ruby circular-primes.rb
real   0m9.984s
user   0m9.980s
sys    0m0.000s