Primes Example [ISO]

Arithmetic and lists are also part of the Jekejeke Prolog programming language. The given example computes the prime numbers up to a given upper bound by the Sieve of Eratosthenes. The graphical intuition behind it is as follows. The sieve starts with listing the integer numbers starting from 2 up to some upper bound m. Here is an example for m=16:


During each iteration we pick the first uncrossed number and cross out the multiples of it. Each picked number will be a prime number. The process stops when no more prime numbers are left. Of course we can also already stop crossing out a little bit earlier, namely when we find a prime number p such that p*p>m:


From the above sieve we can read off that 2, 3, 5, 7, 11 and 13 are the only prime numbers between 2 and 16. We will now go on and implement this sieve in Prolog. We use Prolog lists to represent the sieve. The list will only contain the uncrossed numbers. The first predicate that we need is the predicate that builds the initial list:

integers(Low, High, [Low | Rest]) :-
      Low =< High, !,
      M is Low + 1,
      integers(M, High, Rest).
integers(_, _, []).

The first rule first checks whether we are still inside the lower and upper bound. If yes we return the lower bound as the first list element and recursively call the predicate with an increased lower bound. Otherwise we return an empty list. We can test it for m=16:

?- integers(2,16,X).
X = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

As a next step we need a predicate that is able to cross out multiples of a given number. This predicate will input the sieve before crossing out multiples and the output the sieve after crossing out the sieve. To check multiplicity we use the arithmetic remainder function:

remove([], _, []).
remove([I | Is], P, Nis) :-
      I rem P =:= 0, !,
      remove(Is, P, Nis).
remove([I | Is], P, [I | Nis]) :-
      remove(Is, P, Nis).

The first rule states that nothing needs to be removed from the empty list. The second rule removes the first element of a list if it is a multiple of the given number and then continues recursively. Otherwise the third rule will keep the first element and continue recursively. We can test it also for m=16 and sift two times:

?- integers(2,16,X), remove(X,2,Y), remove(Y,3,Z).
X = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16],
Y = [3, 5, 7, 9, 11, 13, 15],
Z = [5, 7, 11, 13]

We now need a predicate that does the iteration of the crossing out and the collection of the prime numbers, until we have reached the stopping condition. Again we will have input and output argument positions of the predicate. To check the stopping we use the arithmetic multiplication function:

sift([I | Is], High, [I | Is]) :-
     I * I > High, !.
sift([I | Is], High, [I | Ps]) :-
     remove(Is, I, New),
     sift(New, High, Ps).

The first rule expresses our stopping condition. When we have reached p*p>m we will return all the remaining numbers. The second rule will keep the first element, does one crossing out and continues recursively. We can test it for m=16:

?- integers(2,16,X), sift(X,16,Y).
X = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16],
Y = [2, 3, 5, 7, 11, 13]

It is now simple to put the last pieces together. We can define a predicate primes which generate the initial list and then sift through it:

primes(High, R) :-
    integers(2, High, L),
    sift(L, High, R).

We are now done with our implementation and can invoke the predicate for bigger upper bounds than only m=16:

?- primes(16,X).
X = [2, 3, 5, 7, 11, 13]
?- primes(100,X).
X = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Comments