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