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 ((/=).(`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 ((/=).(`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 _  = [[]]
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 ==  = False
| otherwise = isP ps n
p041 = head.filter isPrime .map read.perm "7654321"$ 7