「プロジェクトオイラー問118」の編集履歴(バックアップ)一覧に戻る

プロジェクトオイラー問118 - (2014/03/06 (木) 21:58:45) のソース

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem+118

*Problem 118 「パンデジタル素数集合」 †
1 から 9 の全ての数字を使い, 自由につなげることで 10 進数の数字を作り, 複数の集合を作ることができる. 集合 {2,5,47,89,631} は面白いことに全ての要素が素数である.

1 から 9 の数字をちょうど 1 個ずつ含み, 素数の要素しか含まない集合はいくつあるか?


解法 
 全ての分割組み合わせを重複なく昇順の集合として生成します。
 一つの要素は
 [[1,2,3],[4,5,6],[7,8,9]]の3つで一つ組といった具合です。
 [[4,5,6],[1,2,3],[7,8,9]]とかは同じ組み合わせとみなして生成しません。
 後はそれぞれn個の中一つ一つで全組み合わせを試し全部素数になる順列を見つければよいだけです。  
 上の例なら3!*3!*3!通りの中から探します。 
 集合生成時、各桁の合計が9になったり要素が2個以上で全部2の倍数などの場合素数にならないのでこの場合は除外します。
 
  
 C++などならstd::mapが使えれば[[1,2,3,4],[5,6,7,8,9]]などの場合,[1,2,3,4]は一度計算したらメモ化しておくことで計算を高速化できますがPrologでこれを実装するのは少し大変なのでそこまで高速化してません。
 
 コード実行速度
 
 ?- time(main118).
 [ans,44680]
 % 83,006,818 inferences, 10.031 CPU in 10.038 seconds (100% CPU, 8274823 Lips)
 true.
 10秒はまあまあだと思います。 
 メモ化をつかえればもっと早くなると思います。

 
 
 not_prime(N):-N<2,!.
 not_prime(N):-
 	between(2,N,D),
 	(D*D>N -> !,fail;true),
 	N mod D=:=0,
 	!.
 
 not_prime1(N,_):-N<2,!.
 not_prime1(N,Ps):-
 	member(P,Ps),
 	(P*P>N -> !,fail;true),
 	N mod P=:=0,
 	!.
 
 is_prime(N):-not(not_prime(N)).
 is_prime1(N,Ps):-not(not_prime1(N,Ps)).
 
 
 all2mod0([]):-!.
 all2mod0([X|Xs]):-!,X mod 2=:=0,all2mod0(Xs).
 
 prime_list(N):-
 	between(2,10000,N),
 	is_prime(N).
 
 check(_,KetaSum):-KetaSum mod 9=:=0,!,fail.
 check(List,_):-length(List,Len),Len>1,all2mod0(List),!,fail.
 check(List,KetaSum):-length(List,1),member(KetaSum,[2,3,5,7]),!.
 check(List,_):-length(List,Len),Len>1,!.
 
 
 check_upper(List,_):-length(List,0),!.
 check_upper([E|_],E1):-sort([E,E1],[E,E1]),!.
 
 create_e(List,_,KetaSum,Seed,List1,Seed):-
 	check(List,KetaSum),
 	reverse(List,List1).
 create_e(List,MinN,KetaSum,Seed,ResultList,ResultSeed):-
 	!,
 	select(E,Seed,Seed1),
 	MinN<E,
 	KetaSum1 is KetaSum+E,
 	create_e([E|List],E,KetaSum1,Seed1,ResultList,ResultSeed).
 create_list(ListA,[],ListAA):-!,sort(ListA,ListAA).
 create_list(ListA,Seed,Result):-
 	select(MinN,Seed,Seed1),
 	create_e([MinN],MinN,MinN,Seed1,ListAdd,Seed2),
 	check_upper(ListA,ListAdd),
 	create_list([ListAdd|ListA],Seed2,Result).
 
 to_num([],Num,Ps):-!,is_prime1(Num,Ps).
 to_num(List,Num,Ps):-
 	!,
 	select(E,List,List1),
 	Num1 is Num*10+E,
 	to_num(List1,Num1,Ps).
 
 search([],_):-!.
 search([E|List],Ps):-
 	to_num(E,0,Ps),
 	search(List,Ps).
 
 sorting(List,Ps,1):-
 	member(E,List),
 	search(E,Ps).
 
 
 main118:-
 	findall(E,create_list([],[1,2,3,4,5,6,7,8,9],E),List),
 	findall(P,prime_list(P),Primes),
 	findall(C,sorting(List,Primes,C),Count),
 	length(Count,Ans),
 	write([ans,Ans]).