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

プロジェクトオイラー問４９ - (2014/02/18 (火) 08:44:48) のソース

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


*Problem 49 「素数数列」 †
項差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ.

(i)3つの項はそれぞれ素数である. 
(ii)各項は他の項の置換で表される. 
1, 2, 3桁の素数にはこのような性質を持った数列は存在しないが, 4桁の増加列にはもう1つ存在する.

それではこの数列の3つの項を連結した12桁の数を求めよ.



解法
まずa1<=a2<=a3<=a4でa1～a4は0～9の数という条件を満たす
[a1,a2,a3,a4]というリストを全探索する。
ある[a1,a2,a3,a4]を並べ替えたものを４桁の整数とみて、これが素数であるか判定し
素数のリストを得る。
その中から素数２つを得て、n=差分*２+小さいほうの素数　が素数のリストにありかつｎが一番大きな数であるならそれを答えとする。
計算量は２万回以下。


 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)).
 
 seed(0,_,[]):-!.
 seed(Keta,P,[P|Xs]):-
 	Keta1 is Keta-1,
 	seed(Keta1,P,Xs).
 seed(Keta,P,Xs):-
 	P<9,
 	!,
 	P1 is P+1,
 	seed(Keta,P1,Xs).
 
 seed_w(Perm):-
 	seed(4,0,Perm),
 	sum(Perm,A),
 	A mod 3>0. 
 
 sum([],0):-!.
 sum([X|Xs],Result):-!,sum(Xs,Re),Result is Re+X.
 
 perm([],0):-!.
 perm(Xs,Result):-
 	select(X,Xs,Xs1),
 	perm(Xs1,Re),
 	Result is Re*10+X.
 perm_w(Xs,Result):-
 	perm(Xs,Result),
 	Result>999,
  	is_prime(Result).
 
 
 
 main49:-seed_w(Seed),
 	findall(Perm1,perm_w(Seed,Perm1),Ps),
  	sort(Ps,Perms),
 	member(N1,Perms),
 	member(N2,Perms),
 	N1<N2,
  	N3 is 2*(N2-N1)+N1,
 	N2<N3,
 	member(N3,Perms),
 	write([N1,N2,N3]),
 	fail.