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?

Haskell

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.148s
user   0m0.128s
sys    0m0.016s

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   0m18.254s
user   0m18.124s
sys    0m0.008s

Questions? Comments? Send me an email: [email protected]