このディレクトリの索引


'エラトステネスの篩とは、古代数学者が素数判定法の一種で、
古代数学者エラトステネスが考案したことが記されているためこの名がある。
2以上N以下の順序数の集合から素数と解ったものの倍数を篩に掛けるように
削除していって、すべての要素を検査し終わるまで、すなわち
素数以外の要素がなくなるまでこれを繰り返す。こうして素数集合得るものである。

述語名はこれ以後、"エラトステネスの篩(篩は素数の倍数で篩に掛けるものとする)"と
簡約する'(_Nまで,_素数ならび) :-
        '2以上N以下の順序数集合'(_Nまで,_2以上N以下のの順序数ならび),
        'エラトステネスの篩(篩は素数の倍数で篩に掛けるものとする)'(_2以上N以下の順序数ならび,_素数ならび).

'エラトステネスの篩(篩は素数の倍数で篩に掛けるものとする)'([],[]) :- !.
'エラトステネスの篩(篩は素数の倍数で篩に掛けるものとする)'([A|R1],[A|R2]) :-
        篩は素数の倍数で篩に掛けるものとする(R1,A,L),        
        'エラトステネスの篩(篩は素数の倍数で篩に掛けるものとする)'(L,R2).

篩は素数の倍数で篩に掛けるものとする(R1,A,L) :-
        findall(B,(
                    member(B,R1),
                    \+(0 is B mod A)),L).

'2から始める順序数集合'(_Nまで,_2からNまでの順序数ならび) :-
        findall(M,between(2,_Nまで,M),_2からNまでの順序数ならび).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

mからnの範囲の素数(_m,_n,_mから_nの範囲の素数ならび) :-
        n以下の素数(_n,_n以下の素数ならび),
        findall(_素数,(
                    member(_素数,_n以下の素数ならび),
                    _素数 >= _m),_mから_nの範囲の素数ならび).

n以下の素数(_n以下,_素数ならび) :-
        findall(_数,(
                    between(2,_n以下,_数)),_2以上_n以下の数ならび),
        エラトステネスの篩(_2以上_n以下の数ならび,_素数ならび).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


エラトステネスの篩([],[]) :- !.
エラトステネスの篩([_ある素数|R1],[_ある素数|R2]) :-
        ある素数の倍数を篩に掛ける(_ある素数,_ある素数,[_ある素数|R1],L),
        エラトステネスの篩(L,R2).

ある素数の倍数を篩に掛ける(_,_,[],[]).
ある素数の倍数を篩に掛ける(_ある素数の倍数,_ある素数,[_ある素数の倍数|R1],R2) :-
        _ある素数の倍数_2 is _ある素数の倍数 + _ある素数,
        ある素数の倍数を篩に掛ける(_ある素数の倍数_2,_ある素数,R1,R2),!.
ある素数の倍数を篩に掛ける(_ある素数の倍数_1,_ある素数,[_数|R1],R2) :-
        _ある素数の倍数_1 < _数,
        _ある素数の倍数_2 is _ある素数の倍数_1 + _ある素数,
        ある素数の倍数を篩に掛ける(_ある素数の倍数_2,_ある素数,[_数|R1],R2),!.
ある素数の倍数を篩に掛ける(_ある素数の倍数,_ある素数,[_ある素数の倍数ではない数|R1],[_ある素数の倍数ではない数|R2]) :-
        ある素数の倍数を篩に掛ける(_ある素数の倍数,_ある素数,R1,R2),!.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

エラトステネスの篩([],[]) :- !.
エラトステネスの篩([_素数|R1],[_素数|R2]) :-
        last([_素数|R1],_R1の最終数),
        素数の倍数を篩に掛ける(_R1の最終数,_素数,R1,L),
        エラトステネスの篩(L,R2).

素数の倍数を篩に掛ける(_R1の最終数,_素数,R1,L) :-
        findall(U,(
                    素数の倍数を取る(_R1の最終数,_素数,2,U),
                    (   U > _R1の最終数,!,fail;
                        \+(member(U,R1)))),L).

素数の倍数を得る(M,N,X) :-
        X is M * N.
素数の倍数を得る(M,N,X) :-
        N_2 is N + 1,
        素数の倍数を得る(M,N_2,X).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

エラトステネスの篩([],[]) :- !.
エラトステネスの篩([A|R1],[A|R2]) :-
        エラトステネスの篩(A,R1,L),
        エラトステネスの篩(L,R2) .

エラトステネスの篩(_,_,[],[]) :- !.
エラトステネスの篩(N,[A|R1],R2) :-
        '_要素がNの倍数の時篩に掛かる'(N,A,R1,R2),!.
エラトステネスの篩(N,[_|R1],[A|R2]) :-
        '_要素がNの倍数でない時は残る'(N,R1,R2).

'_要素がNの倍数の時篩に掛かる'(N,A,R1,R2) :-
        0 is A mod N,
        エラトステネスの篩(N,R1,R2).

'_要素がNのでない時は残る'(N,R1,R2) :-
        エラトステネスの篩(N,R1,R2) .

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

エラトステネスの篩([],[]) :- !.
エラトステネスの篩([A|R1],[A|R2]) :-
        A_2 is A + A,
        エラトステネスの篩(A,A_2,R1,L),
        エラトステネスの篩(L,R2) .

エラトステネスの篩(N,N_1,L1,L2) :-
        select(N_1,L1,L3),
        N_2 is N_1 + N,
        エラトステネスの篩(N_2,L3,L2).
エラトステネスの篩(N,N_1,L1,L2) :-
        N_2 is N_1 + N,
        エラトステネスの篩(N_2,L1,L2) .

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

n以下の素数(_n以下,_素数ならび) :-
        findall(_数,(
                    between(2,_n以下,_数)),_2以上_n以下の数ならび),
        Max is truncate(sqrt(_n以下)),
        エラトステネスの篩(Max,_2以上_n以下の数ならび,_素数ならび).

エラトステネスの篩(_,[],[]) :- !.
エラトステネスの篩(Max,[A|R1],[A|R2]) :-
        或る数の倍数を削除する(Max,A,R1,L),
        エラトステネスの篩(Max,L,R2).

或る数の倍数を削除する(Max,A,L1,L) :-
        findall(U,(
                    member(B,L1),
                    或る数の倍数と一致しない(Max,A,B)),L).

或る数の倍数と一致しない(Max,_或る数,B) :-
        或る数の倍数を生成する(_或る数,_倍数),
        (   _倍数 > Max,
            B = _倍数,! ;
            _倍数 > Max,!,fail).

或る数の倍数を生成する(_或る数,_倍数) :-
        或る数の倍数を生成する(2,_或る数,_倍数).

或る数の倍数を生成する(N,_或る数,_倍数) :-
        _倍数 is _ある数 * (N + 1).
或る数の倍数を生成する(N,_或る数,_倍数) :-
        N_2 is N + 1,
        或る数の倍数を生成する(N_2,_或る数,_倍数).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

エラトステネスの篩([],[]) :- !.
エラトステネスの篩([A|R1],[A|R2]) :-
        エラトステネスの篩(A,R1,L),
        エラトステネスの篩(L,R2).

エラトステネスの篩(_,[],[]) :- !.
エラトステネスの篩(N,[A|R1],R2) :-
        0 is A mod N,
        エラトステネスの篩(N,R1,R2),!.
エラトステネスの篩(N,[A|R1],[A|R2]) :-
        エラトステネスの篩(N,R1,R2).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

エラトステネスの篩([],[]) :- !.
エラトステネスの篩([A|R1],[A|R2]) :-
        'R1から、Aの倍数である要素を篩い落とし、Aの倍数ではない要素だけを残す'(R1,A,L),        
        エラトステネスの篩(L,R2).

'R1から、Aの倍数である要素を篩い落とし、Aの倍数ではない要素だけを残す'(R1,A,L) :-
        findall(B,(
                    member(B,R1),
                    \+(0 is B mod A)),L).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

エラトステネスの篩([],[]) :- !.
エラトステネスの篩([A|R1],[A|R2]) :-
        findall(B,(member(B,R1),\+(0 is B mod A)),L),
        エラトステネスの篩(L,R2).