Problem 35 循環素数

問題

解説：
①エラトステネスのふるいによる素数列挙、すべてsosu述語としてassert
②rotate述語で転回した数字をsosu述語で存在するか確認
　すべての転回に関して存在すればretract
　見つかった分カウントをアップ

結構速く動作してると思います（自分の基準では）

% problem 35

% Idx は 9 のみで構成されている必要あり
solve(Idx):-
	retractall(sosu),
	flag(junkan_sosu_cnt, _, 0),
	assert(max(Idx)),
	make_list(Idx,List),
	eratosthenes_sieve(List,List1), % エラトステネスのふるいによる素数列挙
	assert_all(List1),
	rot_chks(List1),
	!,
	flag(junkan_sosu_cnt, Cnt1, Cnt1),nl,
	write(Cnt1).

rot_chks([]):-!.
rot_chks([First|Rest]):-
	rot_chk(First),
	rot_chks(Rest).
rot_chks([_|Rest]):-
	!,
	rot_chks(Rest).
	
rot_chk(Num):-
	!,
	findall(Rot,rotate(Num,Rot),RotLst),
	sort(RotLst,RotLst1),  % delete duplicate numbers like [11,11]
	sosu_assert_chk(RotLst1),
	write(RotLst1),nl,
	length(RotLst1,Len),
	flag(junkan_sosu_cnt, Cnt, Cnt + Len),
	retract_sosu_list(RotLst1).

% リスト内がすべて素数としてassertされているかかェック
sosu_assert_chk([]):-!.
sosu_assert_chk([First|Rest]):-
	sosu(First),
	sosu_assert_chk(Rest).

retract_sosu_list([]):-!.
retract_sosu_list([First|Rest]):-
	retract(sosu(First)),
	retract_sosu_list(Rest).

assert_all([]):-!.
assert_all([First|Rest]):-
	assert(sosu(First)),
	assert_all(Rest).

% 2 ～ Idx までのリストを作成
make_list(Idx,List):-
	make_list_sub(Idx,List,[]).
	
make_list_sub(1,Ret,Ret):-!.
make_list_sub(Idx,Ret,List):-
	Idx1 is Idx - 1,
	make_list_sub(Idx1,Ret,[Idx | List]).
	
% 素数列挙 エラトステネスのふるい
eratosthenes_sieve([],[]):-!.
eratosthenes_sieve([First | Rest],[First | Rest]):-
	max(Max),
	First * First > Max ,
	!.
eratosthenes_sieve([First | Rest], [First | Ret]):-
	erase_baisu(First,Rest,Rest1),
	eratosthenes_sieve(Rest1,Ret).

erase_baisu(_,[],[]):-!.
erase_baisu(Base,[First | Rest],[First | Ret]):-
	First mod Base =\= 0,
	!,
	erase_baisu(Base,Rest,Ret).
erase_baisu(Base,[_ | Rest],Ret):-
	erase_baisu(Base,Rest,Ret).

% Num を回転させた数字が Rot (Choice Pointあり)
% 123 -> 231 , 312
rotate(Num,Rot):-
	number_chars(Num,Chrs),
	length(Chrs,Len),
	rotate_sub(Chrs,Len,Rot).

rotate_sub(_,0,_):-!,fail.
rotate_sub(Chrs,_,RotNum):-
	number_chars(RotNum,Chrs).
rotate_sub([First | Rest],Idx ,Rot ):-
	append(Rest,[First],Rot1),
	Idx1 is Idx -1 ,
	rotate_sub(Rot1,Idx1,Rot).

実行結果：

1 ?- 
% c:/Documents and Settings/Owner/My Documents/Prolog/junkan_sosu.pl compiled 0.02 sec, 25 clauses
1 ?- time(solve(999999)).
***********************(解答伏せます)**********************
% 42,859,931 inferences, 35.094 CPU in 35.156 seconds (100% CPU, 1221298 Lips)
true.