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

プロジェクトオイラー問１１８ - (2014/03/06 (木) 20:20:38) のソース

解法
全ての分割組み合わせを重複なく生成します。
一つの要素は
[[1,2,3],[4,5,6],[7,8,9]]の３つで一つ組といった具合です。
後はそれぞれ３つの中で全組み合わせを試し全部素数になる順列を見つければよいだけです。
集合生成時、各桁の合計が9になったり要素が2個以上で全部２の倍数などの場合素数にならないのでこの場合は除外します。
 
 
 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]).