※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。


Problem 35 「巡回素数」 †

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

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

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



解法
一桁はスペシャルケースとして扱う。
2桁以降は数字に0,2,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).