Problem 41

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

下のを作ってから気がついたけど、この問題実は7桁の素数をひとつ見つければ終わりだから、
"7654321"の置換を昇順に生成して、素数かチェックして、
素数なら出力、合成数なら次の候補へ
というアルゴリズムが高速なはず。
実装はめんどくさいので省略。置換の昇順作成あたりが。

そう考えると、このプログラムはすげー無駄なことしてる。

import Data.Char
import Data.List
sieve (_,((p:ps),qs)) = (ps',(ps++ps',filter ((/=0).(`mod` p)) qs'))
    where (ps',qs') = span (<p*p) qs
primes = iterate sieve([2],([3],[3,5..]))>>=fst

intToList ::Integer -> [Int]
intToList = map(digitToInt).show

isPandigit p = let li = intToList p
               in sort li == [1..(length li)]

pandigits [] = []
pandigits (p:ps) | isPandigit p = p:(pandigits ps)
                 | otherwise = pandigits ps

p041 =maximum.pandigits.takeWhile(<=7654321)$primes

めんどくさいといったが、順列生成はそれはそれで面白いので
なんとなく作ってみた。順列生成速度は速いのかはよく分からないが、
実行は悲しくなるほど速い。
計算量を考えれば当然だが。

import Data.List
sieve (_,((p:ps),qs)) = (ps',(ps++ps',filter ((/=0).(`mod` p)) qs'))
    where (ps',qs') = span (<p*p) qs
primes = iterate sieve([2],([3],[3,5..]))>>=fst

perm ::Eq a =>[a]->Int->[[a]]
perm _ 0 = [[]]
perm [] _ = []
perm xs@(_:_) (n+1)=concat[map (h:)$perm(delete h xs)n|h<-xs]

isPrime ::Integer->Bool
isPrime 1 = False
isPrime n@(m+1) = isP primes n
    where isP (p:ps) n | n < p*p = True
                       | mod n p == 0 = False
                       | otherwise = isP ps n

p041 = head.filter isPrime .map read.perm "7654321"$ 7