Problem 41 「パンデジタル素数」 †
n桁パンデジタルであるとは, 1からnまでの数を各桁に1つずつ持つこととする.
#下のリンク先にあるような数学的定義とは異なる
例えば2143は4桁パンデジタル数であり, かつ素数である. n桁(この問題の定義では9桁以下)パンデジタルな素数の中で最大の数を答えよ.
解法
まず解の候補は
[1]
[1,2]
[1,2,3]
[1,2,3,4]
[1,2,3,4,5]
[1,2,3,4,5,6]
[1,2,3,4,5,6,7]
[1,2,3,4,5,6,7,8]
[1,2,3,4,5,6,7,8,9]
を並べ替えたものです。
まず作れる数は3の倍数であってはいけません。
すると、各桁の和が3の倍数になる組み合わせはすべて排除されます。
3の倍数の判定法よりどう並べ替えても
[1,2,3,4,5]などは3の倍数になってしまいます。
[1,2,3,4]
[1,2,3,4,5,6,7]
を並べ替えたものだけが3の倍数とならないのでこれを全て検討してそのうち素数であるもののリストえます。
最後にリストをソートしてリストの最後に来た数が答えです。
not_prime(P):-P<2,!.
not_prime(2):-!,fail.
not_prime(P):-
between(2,P,Div),
(Div^2>P->!,fail;true),
P mod Div=:=0,
!.
is_prime(P):-!,not(not_prime(P)).
seed([1,2,3,4]).
seed([1,2,3,4,5,6,7]).
perm([],[]).
perm(Seed,[X|Perm]):-
select(X,Seed,Seed1),
perm(Seed1,Perm).
to_num([],0):-!.
to_num([X|Xs],Result):-
to_num(Xs,Re),
Result is Re*10+X.
search(Num):-
seed(Seed),
perm(Seed,Perm),
to_num(Perm,Num),
is_prime(Num).
main41:-
findall(A,search(A),Ans),
sort(Ans,Ans1),
write(Ans1).
最終更新:2014年02月15日 18:07