Euler problems/31 to 40
From HaskellWiki
Revision as of 00:16, 27 September 2012) (replicate coin
The program above can be slightly modified as shown below so it just counts the combinations without generating them.
coins = [1,2,5,10,20,50,100,200] countCoins 1 _ = 1 countCoins n x = sum $ map addCoin [0 .. x `div` coins !! pred n] where addCoin k = countCoins (pred n) (x - k * coins !! pred n) problem_31 = count
Another way: = sum $ map fac)
5 Problem 35
How many circular primes are there below one million?
Solution:
import Data.List (tails, (\\)) 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
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)
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.)]
Or, more cleanly:
import Data.Numbers.Primes (primes, isPrime) test' :: Int -> Int -> (Int -> Int -> Int) -> Bool test' n d f | d > n = True | otherwise = isPrime (f n d) && test' n (10*d) f test :: Int -> Bool test n = test' n 10 (mod) && test' n 10 (div) problem_37 = sum $ take 11 $ filter test $ filter (>7) primes :: Int = elem))