プロジェクトオイラー問３５ - c21coterie @ ウィキ

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

Problem 35 「巡回素数」 †

197は巡回素数と呼ばれる. 桁を回転させたときに得られる数 197, 971, 719 が全て素数だからである.

100未満には巡回素数が13個ある: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, および97である.

100万未満の巡回素数はいくつあるか?

解法
一桁はスペシャルケースとして扱う。
２桁以降は数字に0,２,4,6,8は入らない。
5も当然入らない。
巡回素数に使える数は1,3,7,9だけとなる。
4＾6+4^5+4^3+4^2個の数字を検討するだけ、これなら木構造とか凝ったことをしても対して早くならなさそうです。

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

slide(X,Result):-X<100,!,Result    is  (X mod 10)*10+(X//10).
slide(X,Result):-X<1000,!,Result   is  (X mod 10)*100+(X//10).
slide(X,Result):-X<10000,!,Result  is  (X mod 10)*1000+(X//10).
slide(X,Result):-X<100000,!,Result is  (X mod 10)*10000+(X//10).
slide(X,Result):-X<1000000,!,Result is (X mod 10)*100000+(X//10).



perm([],6):-!.
perm([],Keta):-Keta>1.
perm([X|Xs],Keta):-
	Keta1 is Keta+1,
	member(X,[1,3,7,9]),
	perm(Xs,Keta1).

is_all_slide_ok(_,0):-!.
is_all_slide_ok(Num,Keta):-
	is_prime(Num),
	slide(Num,Num1),
	Keta1 is Keta-1,
	is_all_slide_ok(Num1,Keta1).

to_num([],0):-!.
to_num([X|Xs],Result):-
	to_num(Xs,Re),
	Result is Re*10+X.

circular_prime_list(Num):-
	perm(Perm,0),
	length(Perm,Keta),
	to_num(Perm,Num),
 	is_all_slide_ok(Num,Keta).



main35:-
	findall(Num,circular_prime_list(Num),Nums),
	length(Nums,Ans),
	Ans1 is Ans+4,
	write(Ans1).