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.

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

次のHTML タグと属性が使えます: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>