/* ///////////////////////////////// */ /* 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.