primes (Limit, Ps). :integers (2, Limit, Is), sieve (Is, Ps). integers (Low, High, [Low Rest]) :- Low = < < High, !, M is Low+1, integers (M, High, Rest). integers (Low, High, []). sieve ([], []). sieve ([I | Is], [I]Ps]) - remove (I, Is, New), remove (P, [], []). sieve (New, Ps). remove (P, [I | Is], [I|Nis]) :- not (0 is I mod P), !, remove (P, Is, Nis). remove (P, [I Is], Nis) :- 0 is I mod P, !, remove (P, Is, Nis). Figure 4.6 The Sieve of Eratosthenes in Prolog (adapted from Clocksin and Mellish [1994])