Project Euler 解答

Project Euler Problem 041

Project Euler Problem 041

import Data.List import Data.Char primes :: [Integer] primes = 2:f [3] [3,5..] where f (x:xs) ys = ps ++ f (xs ++ ps) [z|z<-qs,z`rem`x/=0] where (ps,qs) = span(< x*x) ys isPrime :: Integer -> Bool isPrime 1 = False isPrime nn = imp nn primes where imp n pp@(p:ps) = if n [a] -> [[a]] perm [] = [[]] perm l = [x:y | x<-l,y<-perm (delete x l)] --辞書順なので大きい順に試せる。List.permutationsは非辞書順 ispan :: Show a => a -> Bool ispan n = sort r == r where r = show n --ispan n = ap (==) sort $ show n --import Control.Monadすればちょっと短い --2,3,5,6,8,9桁の数はすべて3の倍数なので素数にならない targets :: [[Char]] targets = filter ((/=0).(`rem`3).sum .map digitToInt) $ ("9876543210" : (init $ tails "987654321")) ans :: [Char] ans = head $ concatMap (\dst -> [v | v<-perm dst,isPrime (read v)]) targets -- 7652413 main :: IO () main = print ans

since 2013