Prolog

Prolog is weird. There's no other way to say it. First take Logic, reduce it to the most boring level possible, eliminate everything that makes programming enjoyable, and what you have left is prolog. The following example uses lists and tail recursion in a pretty standard way to implement the Sieve algorithm.

This code runs under The Windows implementation of GNU prolog. I guarantee you, if you try and run this on your own without instructions, you'll never figure it out. (Well, given enough time you will, but you won't want to spend that much time on something like this.)

1. Install GNU prolog using the default options.
2. Add an environment variable LOCALSZ to your system with a value of 65536.
3. Save the code from the link below on your desktop, and change the suffix to ".pl".
4. Start the GNU prolog console from the desktop Icon.
5. Type: [sievee]. Make sure to include the period and make sure that "sievee" is in lower case.
6. Type: sieve(1000). Make sure to include the period.
7. Type a semicolon in response to the prompt.
8. Type <control-D> (the character) to quit.

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

Click Here for the actual code.