#### Prime Numbers

```trail = 2048
domains
int  = integer
ints = reference int*
predicates
is_prime(int)
is_prime_1(int,int,int)
primes(int,ints)
primes_dl(int,int,int,int,ints,ints,ints)
is_prime_2(ints,int,int)
next_sqrt(int,int,int,int)
clauses

/* is_prime(N) is true if N is a prime number.                             */
/*   This divides N by all integers less than or equal to the square root  */
/*   of N, failing if the integer is a factor of N.                        */
is_prime(2):-!.
is_prime(P):-
P > 2,
P mod 2 = 1,
is_prime_1(3, P).

is_prime_1(I, P):-
I * I > P, !.
is_prime_1(I, P):-
P mod I > 0,
I1 = I + 2,
is_prime_1(I1, P).

/* primes(N, Primes) is true if Primes is an ordered list of all prime     */
/*   numbers less than or equal to N.                                      */
/*   Each successive integer is checked to be prime by dividing it by all  */
/*   preceding primes which are less than or equal to the square root of   */
/*   the integer.  Note that square roots are calculated without using     */
/*   sqrt/1.  Changing the code to test sucessive odd integers is left as  */
/*   an exercise for the reader!                                           */
primes(N, Primes):-
N > 2,
primes_dl(3, N, 0, 1, [2|Primes0], Primes0, Primes).

primes_dl(I, N, J, SqrtI, Primes0, Primes2, Primes):-
I <= N,
is_prime_2(Primes0, I, SqrtI),
!,
I1 = I + 1,
next_sqrt(J, SqrtI, J1, SqrtI1),
Primes2 = [I|Primes1],
primes_dl(I1, N, J1, SqrtI1, Primes0, Primes1, Primes).
primes_dl(I, N, J, SqrtI, Primes0, Primes1, Primes):-
I <= N,
!,
I1 = I + 1,
next_sqrt(J, SqrtI, J1, SqrtI1),
primes_dl(I1, N, J1, SqrtI1, Primes0, Primes1, Primes).
primes_dl(_, _, _, _, Primes, [], Primes).

/* is_prime_2(Primes, I, SqrtI) is true if I is a prime number, where      */
/*   Primes is the ordered list of all prime numbers less than I, and      */
/*   SqrtI is the floor of the square root of I.                           */
is_prime_2([Prime|Primes], I, SqrtI):-
Prime <= SqrtI,
!,
I mod Prime > 0,
is_prime_2(Primes, I, SqrtI).
is_prime_2(_, _, _).

/* next_sqrt/4 is a generator of the values of the floor of the square     */
/*   root of successive integers.                                          */
next_sqrt(0, Sqrt0, J, Sqrt1):-
!,
Sqrt1 = Sqrt0 + 1,
J = 2 * Sqrt1.
next_sqrt(J0, Sqrt0, J, Sqrt0):-
J = J0 - 1.
```