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

「プロジェクトオイラー問３５」(2014/02/14 (金) 17:15:25) の最新版変更点

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

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

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万未満の巡回素数はいくつあるか?



解法
配列つかえたら素数を篩にかけて、それを参照すればいいだけなのですが。
Prologにはリストしかないから効率的な方法を只今考え中。
木を使うのが一番オーソドックスに思えるけれど？
一桁はスペシャルケースとして扱うとして。
２桁以降は数字に0,２,4,6,8は入らない。
5も入らない。
巡回素数に使える数は1,3,7,9だけとなる。
2＾12個の数字を検討するだけ、これなら木構造とか凝ったことをしても対して早くならなさそうです。



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

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