Problem 10 二百万以下の素数の和

プロジェクトオイラーをPrologで解く

問題

プロジェクトオイラーは一度素数列挙ロジックを作るとあちこちで使いまわせる。


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

コメントを残す

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

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