% ==========================================================================
% $Id: prime_num.pl,v 1.1 2014/01/23 04:34:04 jlang Exp $
% CSI2120 example Code for lecture 6
% ==========================================================================
% (C)opyright:
%
%   Robert Laganiere, Jochen Lang
%   EECS, University of Ottawa
%   800 King Edward Ave.
%   Ottawa, On., K1N 6N5
%   Canada. 
%   http://www.eecs.uottawa.ca/~jlang
% 
% Creator: jlang (Jochen Lang)
% Email:   jlang@eecs.uottawa.ca
% ==========================================================================
% $Log: prime_num.pl,v $
% Revision 1.1  2014/01/23 04:34:04  jlang
% Created examples for lecture 6
%
% ==========================================================================
generateInt(0,[]) :- !.
generateInt(N,[N|Xs]):- N > 0,
    N1 is N-1,generateInt(N1,Xs).

% remove multiples of X from the list [H|T]
removeMultiple(_,[],[]).                % boundary case   
removeMultiple(X,[H|T],Result) :- H>X,  % Test if H is to be removed
    H mod X =:= 0,                      % Check if current H is a multiple of X
    removeMultiple(X,T,Result),!.       % remove H and recurse
removeMultiple(X,[H|T],[H|Result]) :-   % Not a multiple keep H
    removeMultiple(X,T,Result).         % recurse

% Sieve of Eratosthenes: 
% ==========================================================================
% $Id: prime_num.pl,v 1.1 2014/01/23 04:34:04 jlang Exp $
% CSI2120 example Code for lecture 6
% ==========================================================================
% (C)opyright:
%
%   Robert Laganiere
%   EECS, University of Ottawa
%   800 King Edward Ave.
%   Ottawa, On., K1N 6N5
%   Canada. 
%   http://www.eecs.uottawa.ca/~jlang
% 
% Creator: jlang (Jochen Lang)
% Email:   jlang@eecs.uottawa.ca
% ==========================================================================
% $Log: prime_num.pl,v $
% Revision 1.1  2014/01/23 04:34:04  jlang
% Created examples for lecture 6
%
% ==========================================================================
% N is the highest number
% Li (2nd arg) is the current list of numbers to be tested
% L (3rd arg) is the result
removeAllMultiples(_,[],[]).            % no numbers left
removeAllMultiples(1,L,L).              % division by 1 
removeAllMultiples(N,Li,L):- N>1,             
    removeMultiple(N,Li,LL),            % start with N
    N1 is N-1,                          % work towards 1
    removeAllMultiples(N1,LL,L),!.      % call ourselves

primeNum(N,L):- generateInt(N,Li),      % top level
    removeAllMultiples(N,Li,L).