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