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

プロジェクトオイラー問３７ - (2014/02/14 (金) 19:29:10) のソース

*Problem 37 「切り詰め可能素数」 †
3797は面白い性質を持っている. まずそれ自身が素数であり, 左から右に桁を除いたときに全て素数になっている (3797, 797, 97, 7). 同様に右から左に桁を除いたときも全て素数である (3797, 379, 37, 3).

右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ.

注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.


解法
切り詰め可能な素数は最後は必ず、2,3,5,7となります。
逆に考えると右を削るの逆操作を考えると、右に付け足すと考えても目的の数は手に入ります。
そして幸運なことに一桁目を素数から初めて永遠に右に付け足すことはできません。
２桁以上が手に入ったら左を全て削れるか試して合格した数を答えとします。
ね、簡単でしょ？


 not_prime(P):-P<2,!.
 not_prime(2):-!,fail.
 not_prime(P):-
 	between(2,P,Div),
 	(Div^2>P->!,fail;true),
 	P mod Div=:=0,
 	!.
 is_prime(P):-!,not(not_prime(P)).
 
 
 addR(N,_,_,_):-
 	not_prime(N),
 	!,
 	fail.
 addR(N,N,Keta,Keta):-N>10.
 
 addR(N,ResultN,Keta,ResultKeta):-
 	member(Add,[1,3,7,9]),
 	N1 is N*10+Add,
 	Keta1 is Keta+1,
 	addR(N1,ResultN,Keta1,ResultKeta). 
 
 dellL(N,_):-
 	not_prime(N),
 	!,
 	fail.
 dellL(N,_):-N<10,!.
 dellL(N,Keta):-
	N1 is N mod (10^Keta),
  	Keta1 is Keta-1,
 	dellL(N1,Keta1).
 
 search(N1):-
 	member(N,[2,3,5,7]),
 	addR(N,N1,0,Keta),
 	dellL(N1,Keta).
  
 sum([],0):-!.
 sum([X|Xs],Result):-sum(Xs,Re),Result is Re+X.
 
 main37:-
 	findall(N,search(N),Nums),
 	write(Nums),
 	sum(Nums,Ans),
 	write(Ans).