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

「プロジェクトオイラー問５１」(2014/02/18 (火) 14:03:13) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

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


*Problem 51 「素数の桁置換」 †
 *3の第1桁を置き換えることで, 13, 23, 43, 53, 73, 83という6つの素数が得られる.
 56**3の第3桁と第4桁を同じ数で置き換えることを考えよう. この5桁の数は7つの素数をもつ最初の例である: 56003, 56113, 56333, 56443, 56663, 56773, 56993. よって, この族の最初の数である56003は, このような性質を持つ最小の素数である. 
 桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ. (注:連続した桁でなくても良い)



解法
変更するのが1,2,4,5つの桁数だと。
一気に変更した時各桁の和を３で割った余りが0,1,2にばらけます
それ以外の数字は変更がないのですから８個の数のうちどれかが３で割れる数になってしまいます。
変更するのは３の倍数桁だけです。
６ケタや９桁の可能性もあります。
それだと７ケタ以上を検討する必要があり計算が大変です。
そこで小さい桁からヒュースティリックに試していき答えが出るまで桁を伸ばす方法にしました。



 not_prime(P):-P<2,!.
 not_prime(P):-
 	between(2,P,Div),
 	(Div^2>P->!,fail;true),
 	P mod Div=:=0,
 	!.
 is_prime(P):-!,not(not_prime(P)).
 
 to_num([X],X):-X>0,!.
 to_num([X|Xs],Result):-
 	!,
 	to_num(Xs,Re),
 	Result is Re*10+X.
 
 commitA([],[]):-!.
 commitA([a|Xs],[Y|Result]):-
 	!,
 	member(Y,[0,1,2,3,4,5,6,7,8,9]),
 	commitA(Xs,Result).
 commitA([b|Xs],[b|Result]):-
 	!,
 	commitA(Xs,Result).
 
 commitB(_,[],[]):-!.
 commitB(Num,[b|Xs],[Num|Result]):-
 	!,
 	commitB(Num,Xs,Result).
 commitB(Num,[X|Xs],[X|Result]):-
 	!,
 	commitB(Num,Xs,Result).
 seed([a,b,b,b]).
 seed([a,a,b,b,b]).
 seed([a,a,a,b,b,b]).
 
 commit_perm([],[]):-!.
 commit_perm(Xs,[Y|Ys]):-!,
 	select(Y,Xs,Xs1),
 	commit_perm(Xs1,Ys).
 
 search2(Perm,Num):-
 	between(0,9,N),
 	commitB(N,Perm,Perm1),
 	to_num(Perm1,Num),
 	is_prime(Num).
 
 search(AnsList):-
 	seed(Seed),
 	findall(Perm0,commit_perm(Seed,Perm0),Perms),
 	sort(Perms,Perms1),
  	member(Perm1,Perms1),
 	commitA(Perm1,Perm2),
 	findall(P,search2(Perm2,P),AnsList),
 	length(AnsList,Len),
 	Len=:=8
 	.
 main51:-
 	search(AnsList),
 	write(AnsList).