このディレクトリの索引

#  包除原理
#  1以上n以下の整数で、a1,a2,....amのうち、すくなくとも1つで割り切れるものの個数を計算しなさい。
#  1 =< n =< 10 ^ 8
#  1 =< m =< 15
#  

'1以上n以下の整数をランダムに発生させる'(L) :-
        _m is (random mod 15) + 1,
        length(L,_m),
        findall(_n,(
                    append(L0,[_n|_],L),
                    ランダム数を得る(L0,_n)),
                L).

ランダム数を得る(L0,_n) :-
        _n is (random mod 100000000) + 1.
        \+(append(_,[_n|_],L0)),!.
ランダム数を得る(L0,_n) :- ランダム数を得る(L0,_n).

'1以上n以下の整数で、a1,a2,....amのうち、すくなくとも1つで割り切れるものの個数を計算する'(L,_個数) :-
        var(L),
        '1以上n以下の整数をランダムに発生させる'(L),
        すくなくとも1つで割り切れるものの個数を計算する(L,_個数),!.
'1以上n以下の整数で、a1,a2,....amのうち、すくなくとも1つで割り切れるものの個数を計算する'(L,_個数) :-
        \+(var(L)),
        すくなくとも1つで割り切れるものの個数を計算する(L,_個数).

すくなくとも1つで割り切れるものの個数を計算する(_整数ならび,_個数) :-
        すくなくとも1つで割り切れるもの(_整数ならび,_割り切れない数ならび),
        length(_割り切れない数ならび,_個数).

すくなくとも1つで割り切れるもの([],[]).
すくなくとも1つで割り切れるもの([N1|R1],L) :-
        割り切れる数字を除外(N1,R1,L1),
        すくなくとも1つで割り切れるもの(L1,L2),
        append(L1,L2,L).

割り切れる数字を除外(_,[],[]).
割り切れる数字を除外(N,[N2|R2],[N2|R3]) :-
        \+(0 is N2 mod N),
        割り切れる数字を除外(N,R2,R3).
割り切れる数字を除外(N,[N2|R2],R3) :-
        0 is N2 mod N,
        割り切れる数字を除外(N,R2,R3).