:- module(_, [primes/2], [assertions, regtypes, nativeprops]).

:- entry primes(Limit, Ps) : num * term.
:- pred primes(Limit, Ps) : num * term.

primes(Limit, Ps) :-
	primes_(Limit, Ps).

:- pred primes(Limit, Ps) : num * term => num * numlist.

primes_(Limit, Ps) :-
        integers(2, Limit, Is),
        sift(Is, Ps).

:- pred integers(Low, High, Xs) : num * num * term => num * num * numlist.
integers(Low, High, [Low | Rest]) :-
        Low =< High, !,
        M is Low + 1,
        integers(M, High, Rest).
integers(_,_,[]).

:- pred sift(Is, Ps) : numlist * term => numlist * numlist.
sift([], []).
sift([I | Is], [I | Ps]) :-
        remove(Is, I, New),
        sift(New, Ps).

:- pred remove(Is, P, Ps) : numlist * num * var => numlist * num * numlist.
remove([], _, []).
remove([I | Is], P, [I | Nis]) :-
        IModP is I mod P,
        IModP =\= 0, !,
        remove(Is, P, Nis).
remove([_I | Is], P, Nis) :-
        remove(Is, P, Nis).

:- regtype numlist/1.
numlist([]).
numlist([X|Xs]) :-
    num(X),
    numlist(Xs).
