project-euler / Haskell / 035.hs

{- Problem #35
 - Find the total number of circular primes less than 1,000,000.
 -
 - First we're going to need a function to rotate a number.  We can use
 - Haskell's convenient read / show pairing to convert from numerics to strings
 - and back, so we can write an easy string rotation function.
 -
 - Normally we could cut out numbers that end in 0, 2, 4, 5, 6, or 8 as being
 - not prime, but in this case we can do even better.  Since the numbers will be
 - fully rotated, any number that simply contains one of these digits in any
 - position can be eliminated.
 -
 - One convenience function will produce all possible rotations of a given
 - number as a list.  In the final solution, we will make sure that all of these
 - rotations satisfy the predicate of being prime, before they make it into the
 - final list.  The length of this list of circular prime numbers is, of course,
 - the answer that we're looking for.
 -}

import Data.List

rotl :: String -> Int -> String
rotl s 0 = s
rotl (h:t) n = rotl (t ++ [h]) (n-1)

-- note that this function excludes '2' and '5',
-- so make sure to add them later as special cases
valid :: [String]
valid = [ y | y <- map show [ 2 .. 1000000 ] , all (\x -> notElem x y) ['0', '2', '4', '5', '6', '8'] ]

allRot :: String -> [String]
allRot s = [ rotl s x | x <- [ 0 .. length s - 1 ] ]

isPrime :: Integer -> Bool
isPrime x = [y | y <- [2 .. floor $ sqrt $ fromInteger x], x `mod` y == 0] == []

solution = length [x | x <- valid , all (isPrime . read) $ allRot x] + 2
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.