このディレクトリの索引
http://hibari.2ch.net/test/read.cgi/tech/1320365280/414
#  [1] 授業単元: アルゴリズム  
#  [2] 問題文(含コード&リンク):  
#  整数nを入力、2以上nイカの全ての素数およびその素数の累積を表示(while文を使用) 
#  例) n=15の時: 
#  素数:2,3,5,7,11,13 累積:41 
#  

:- dynamic(階乗保存計算/2).

'2以上n以下の素数ならび'(_n,_素数ならび,_累計) :-
        '2以上n以下の素数ならび'(2,_n,[2],_素数ならび,2,_累計),

'2以上n以下の素数ならび'(N,_n,_素数ならび,_素数ならび,S,S) :-
        N > _n,!.
'2以上n以下の素数ならび'(N,_n,L1,_素数ならび,S1,S) :-
        奇数(N),
        既に計算済みの素数では割り切れない(N,L1),
        ウィルソンの定理による素数判定(N,素数です),
        N2 is N + 1,
        append(L1,[N],L2),
        S2 is S1 + N,
        '2以上n以下の素数ならび'(N2,_n,L2,_素数ならび,S2,S),!.
'2以上n以下の素数ならび'(N,L1,_素数ならび,S1,S) :-
        N2 is N + 1,
        '2以上n以下の素数ならび'(N2,_n,L1,_素数ならび,S1,S).

既に計算済みの素数では割り切れない(N,[]) :- !.
既に計算済みの素数では割り切れない(N,[M|R]) :-
        0 is N mod M,!,
        fail.        
既に計算済みの素数では割り切れない(N,[M|R]) :-
        既に計算済みの素数では割り切れない(N,R).

ウィルソンの定理による素数判定(X,素数です) :-
        X > 0,
        Y is X - 1,
        階乗保存計算(Y,Z),
        0 is (Z + 1) mod X,!.
ウィルソンの定理による素数判定(X,素数ではありません) :-
        X > 0,
        Y is X - 1,
        階乗保存計算(Y,Z),
        \+(0 is (Z + 1) mod X),!.

階乗保存計算(0,1) :- !.
階乗保存計算(1,1) :- !.
階乗保存計算(N,X) :-
        N2 is N - 1,
        階乗保存計算(N2,Y),
        X is N * Y,
        asserta((階乗保存計算(N,X) :- !)).

奇数(N) :-
        1 is N mod 2.