/* ///////////////////////////////// */
/* Name: Peter M. Maurer             */
/* Program: Sieve of Eratosthenes    */
/* Due: Never                        */
/* Language: Prolog                  */
/* ///////////////////////////////// */



/* makeit(N,K) make an initial sieve of size N and return it in K.   */
makeit(1,[0,0]).
makeit(N,0) :-
    N =< 0.
makeit(N,[0,K]) :-
    N > 1,
    M is N-1,
    makeita(M,K).
makeita(N,[0,K]) :-
    N > 0,
    M is N-1,
    makeitb(M,K).
makeita(N,0) :-
    N =< 0.
makeitb(N,0) :-
    N =< 0.
makeitb(1,[1,1]).
makeitb(N,[1,K]) :-
    N > 1,
    M is N-1,
    makeitb(M,K).

/* printing the primes */
printit(M,N,_) :-
    M = N,
    nl.
printit(M,N,_) :-
    M > N,
    nl.
printit(M,N,[A,B]) :-
    M < N,
    A = 0,
    K is M+1,
    printit(K,N,B).
printit(M,N,[A,B]) :-
    M < N,
    A \= 0,
    K is M+1,
    write(M),
    write(' is prime'),
    nl,
    printit(K,N,B).

/* trimmit searches the list looking for ones. */

trimmit(M,N,K,T) :-
    N =< M,
    T is K.

trimmit(M,N,[A,B],[0,Z]) :-
    M < N,
    A = 0,
    K is M + 1,
    trimmit(K,N,B,Z).

/* we found a 1, now eliminate all multiples */
trimmit(M,N,[A,B],[1,Z]) :-
    M < N,
    A \= 0,
    K is M + 1,
    rollit(K,N,1,M,B,Q),
    trimmit(K,N,Q,Z).

/* rollit looks for the next multiple of J (arg 4) and zeros it out */
rollit(M,N,_,_,A,Z) :-
    N =< M,
    Z is A.

rollit(M,N,I,J,[A,B],[A,Z]) :-
    M < N,
    I < J,
    K is I + 1,
    P is M + 1,
    rollit(P,N,K,J,B,Z).

rollit(M,N,I,J,[_,B],[0,Z]) :-
    M < N,
    J =< I,
    P is M + 1,
    rollit(P,N,1,J,B,Z).


/* The main sieve */
sieve(N) :-
    N > 2,
    makeit(N,K),
    trimmit(0,N,K,T),
    printit(0,N,T).

sieve(N) :-
    N < 3,
    write('Sieve Arg must be 3 or greater'),
    nl.