解説：
①エラトステネスのふるいによる素数列挙、すべてsosu述語としてassert
②rotate述語で転回した数字をsosu述語で存在するか確認
すべての転回に関して存在すればretract
見つかった分カウントをアップ
結構速く動作してると思います（自分の基準では）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
% 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 2 3 4 5 6 7 8 |
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. |