「プロジェクトオイラー問４１」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問４１ - (2014/02/15 (土) 18:07:48) のソース

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]
を並べ替えたものです。
まず作れる数は３の倍数であってはいけません。
すると、各桁の和が３の倍数になる組み合わせはすべて排除されます。
３の倍数の判定法よりどう並べ替えても
[1,2,3,4,5]などは３の倍数になってしまいます。

[1,2,3,4]
[1,2,3,4,5,6,7]
を並べ替えたものだけが３の倍数とならないのでこれを全て検討してそのうち素数であるもののリストえます。
最後にリストをソートしてリストの最後に来た数が答えです。

 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).