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.

Turbo Prolog Index     Home Page