Prolog でも 100 までの素数を列挙

番外編。Prolog でも素数列挙してみた。*1 *2

prime.pl

:- dynamic prime/1.
non_prime(N) :- prime(P), P < N, N mod P =:= 0.

gen_prime(N) :- not(non_prime(N)), format("~d ", N), assert(prime(N)).
gen_prime(_).

gen_prime(P, MAX) :- MAX < P, !.
gen_prime(P, MAX) :- gen_prime(P), P2 is P + 1, gen_prime(P2, MAX).

結果

1 ?- ['prime.pl'].
% prime.pro compiled 0.00 sec, 1,724 bytes

Yes
2 ?- gen_prime(2, 100).
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Yes

見つけた素数を、prime(P). としてどんどん登録していくコードを作ってみました。
non_prime の実装は、Prolog ならではかと予想してたり。

*1:SWI-Prolog Multi-Threaded, version5.2.0

*2:そういや Prolog が LL 言語だという話は聞かないような気が。Lisp = LL だとはよく聞くけど。