「プロジェクトオイラー問１１８」の編集履歴（バックアップ）一覧はこちら

「プロジェクトオイラー問１１８」(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]]の３つで一つ組といった具合です。
 [[4,5,6],[1,2,3],[7,8,9]]とかは同じ組み合わせとみなして生成しません。
 後はそれぞれ３つの中で全組み合わせを試し全部素数になる順列を見つければよいだけです。  
 上の例なら３！*３！*３！通りの中から探します。 
 集合生成時、各桁の合計が9になったり要素が2個以上で全部２の倍数などの場合素数にならないのでこの場合は除外します。
 
 　
 Ｃ++などならstd::mapが使えれば[[1,2,3,4],[5,6,7,8,9]]などの場合,[1,2,3,4]は一度計算したらメモ化しておくことで計算を高速化できますがＰｒｏｌｏｇでこれを実装するのは少し大変なのでそこまで高速化してません。
 
 コード実行速度
 
 ?- time(main118).
 [ans,44680]
 % 83,006,818 inferences, 10.031 CPU in 10.038 seconds (100% CPU, 8274823 Lips)
 true.
 １０秒はまあまあだと思います。 
 メモ化をつかえればもっと早くなると思います。

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

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

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