プロジェクトオイラーは一度素数列挙ロジックを作るとあちこちで使いまわせる。
% problem 10 solve(Idx):- assert(max(Idx)), make_list(Idx,List), eratosthenes_sieve(List,List1), % エラトステネスのふるいによる素数列挙 add_all(List1,Sum), write(Sum). add_all([],0):-!. add_all([First|Rest],Ret):- add_all(Rest,RestSum), Ret is First + RestSum. 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).
実行結果:
1 ?- time(solve(2000000)). XXXXXXXXXXX % 91,150,992 inferences, 76.484 CPU in 77.969 seconds (98% CPU, 1191760 Lips) true.
コメントを残す