Problem 118

http://projecteuler.net/index.php?section=problems&id=118

いたって普通の解法だと思う。

import Data.List
import Number
permPrime :: [Char] -> Integer
permPrime = genericLength.filter isPrime'.map read.permutations

comb _ 0 = [[]]
comb [] _ = []
comb (x:xs) (n+1) = map (x:) (comb xs n) ++ comb xs (n+1)

count _ [] = 1
count pre ds = sum [c ds q | m<-[min'..max']++len, q<-dropWhile (lt pre)$ comb ds m]
    where min' = length pre
          max' = length ds `div` 2
          len  = if length ds == 9 then [] else [length ds]
          lt xs ys = (read::[Char]->Integer) xs > read ys
          c ds q | permPrime q /= 0 = permPrime q * count q (ds\\q)
                 | otherwise = 0

main = print.count "0" $ "123456789"

数は全部ソートされていると考えて e.g. {2,5,47,89,631}->{2,5,47,89,136}
候補を昇順に列挙して、チェック。
探索範囲を狭くするためにちょっとだけ、工夫。
あんまり速くないけど、8桁の素数チェックは不可避だと思われるので（根拠は無い）、こんなものか？