Prime Numbers

Test if a number is prime

This divides P by all odd integers less than or equal to the square root of P, failing if the integer is a factor of P.

/* is_prime(P) is true if P is a prime number.                             */
is_prime(2):-!.
is_prime(P):-
  P > 2,
  P mod 2 =:= 1,
  SqrtP is sqrt(P),
  is_prime_1(3, P, SqrtP).

is_prime_1(I, _, SqrtP):-
  I > SqrtP, !.
is_prime_1(I, P, SqrtP):-
  P mod I > 0,
  I1 is I + 2,
  is_prime_1(I1, P, SqrtP).
Generate a list of primes

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) is true if Primes is an ordered list of all prime     */
/*   numbers less than or equal to N.                                      */
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 is 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 is 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, Sqrt):-!,
  Sqrt is Sqrt0 + 1,
  J is 2 * Sqrt.
next_sqrt(J0, Sqrt0, J, Sqrt0):-
  J is J0 - 1.

LPA Index     Home Page