% prime(+X)
% True iff X is prime.
prime(2).
prime(3).
prime(X) :-
    X > 3, X mod 2 =\= 0,
    \+ has_factor(X, 3).



% has_factor(+X, +Y)
% True if X has at least one divisor equal to L+2k (k=0,1,...)
has_factor(N, L) :-
    N mod L =:= 0, !.
has_factor(N, L) :-
    L * L < N,
    L2 is L+2,
    has_factor(N, L2).