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 _  = [[]]
comb [] _ = []
comb (x:xs) (n+1) = map (x:) (comb xs n) ++ comb xs (n+1)
count _ [] = 1
count pre ds = sum ++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 /=  = permPrime q * count q (dsq)
| otherwise = 
main = print.count "0" $ "123456789"

数は全部ソートされていると考えて e.g. {2,5,47,89,631}->{2,5,47,89,136}

候補を昇順に列挙して、チェック。

探索範囲を狭くするためにちょっとだけ、工夫。

あんまり速くないけど、8桁の素数チェックは不可避だと思われるので(根拠は無い)、こんなものか?

More Reading
Newer// Problem 111
Older// Problem 120