Adventures in Prolog - Some more Primes

Again, we are going to tackle some problems mentioned in the list of 99-Prolog problems. Today's post builds upon the gcd predicate defined last time to attack problems:

• P31 = is_prime


• P35 = prime_factors


• P36 = prime_factors_mult


• P39 = prime_list

Now, building on the previously defined gcd predicate, on may define a prime inductively:

• a prime is a number which is only (divisible by one and itself)


• the smallest prime is 2


• any number greater than 2 is either composite or prime

Building on this definition we may translate the smallest prime into a Prolog predicate quite easily. To determine the primeness/composibility of any number greater than 2, one may use the gcd predicate. Recalling that a prime p is a number which cannot be divided by any number in ]1, p[, the following predicate may be given:

is_prime(2) :- !.
is_prime(3) :- !.
is_prime(X) :-
  X >= 2,
  UpperBound is round(sqrt(X)) + 1,
  is_prime_t(X, 2, UpperBound), !.

is_prime_t(_, UpperBound, UpperBound).
is_prime_t(X, CurrentFactor, UpperBound) :-
  gcd(X, CurrentFactor, GCD),
  GCD = 1, !,
  NewFactor is CurrentFactor + 1,
  is_prime_t(X, NewFactor, UpperBound).

As can be seen above, two elementary cases (2 and 3) are given and any number not 2 or 3 is checked for primeness. Instead of checking composibility of a prime p for any number in ]1, p[, one may use any number in ]1, square_root(p)]. The reason why I used the rounded value of the square root + 1 is the case of checking 4 which would be determined as a prime because of:

is_prime_t(4, 2, 2).

Instead of the + 1, we might also a check on whether some number is even. Since we know that 2 is not only the smallest prime but also the only even prime number, such a check might greatly enhance the solution search.

Using this definition of is_prime, we might define the prime_list predicate quite easily. A prime list is generated from any number within some interval [a, b], which is prime. We might differentiate three cases (where the last is for convenience) in the definition of prime_list:

1. the interval is [a,b] where a=b


2. the interval is [a,b] where a<b


3. the interval is [a,b] where b<a

Case one results in a list containing one prime if a is itself a prime number. Case 3 will be mapped to case 2 where a and b are switched. This results in a possible prime_predicate as follows:

prime_list(X, X, [X]) :-
  is_prime(X), !.

prime_list(X, X, []) :- !.

prime_list(X, Y, L) :-
  X > Y,
  prime_list_t(Y, X, [], L), !.
 
prime_list(X, Y, L) :-
  prime_list_t(X, Y, [], L), !.
 
prime_list_t(X, X, CurrentPrimes, OutPrimes) :-
  is_prime(X), !,
  append(CurrentPrimes, [X], OutPrimes);
  OutPrimes = CurrentPrimes.

prime_list_t(X, Y, CurrentPrimes, OutPrimes) :-
  is_prime(X), !,
  append(CurrentPrimes, [X], NewPrimes),
  Z is X + 1,
  prime_list_t(Z, Y, NewPrimes, OutPrimes).
 
prime_list_t(X, Y, CurrentPrimes, OutPrimes) :-
  Z is X + 1,
  prime_list_t(Z, Y, CurrentPrimes, OutPrimes).

The last problem to cover is the prime factorization of some given number. This problem is handled by the two predicates prime_factors and prime_factors_mult. Where the first contains each (possibly duplicate) prime factor and prime_factors_mult delivers a power representation of the prime factors of some given number. The approach taken is quite simple, again the factorization of a prime number contains itself (and one which is not included). Also, any composite number can be represented uniquely by a product of prime factors. For example, 4 = 2 * 2 or 12 = 2 * 2 * 3. Now, provided this property of a natural number we may define our two predicates like this:

prime_factors(0, []) :- !.
prime_factors(1, []) :- !.
prime_factors(X, [X]) :- is_prime(X), !.
prime_factors(X, Out) :-
  prime_factors_t(X, 2, [], Out), !.
  
prime_factors_t(1, _, Out, Out).

prime_factors_t(X, TestFactor, CurrentFactors, Out) :-
  gcd(X, TestFactor, GCD),
  GCD \== 1, !,
  append(CurrentFactors, [GCD], NewFactors),
  Z is X / TestFactor,
  prime_factors_t(Z, TestFactor, NewFactors, Out).
  
prime_factors_t(X, TestFactor, CurrentFactors, Out) :-
  NewTestFactor is TestFactor + 1,
  prime_factors_t(X, NewTestFactor, CurrentFactors, Out).
  
prime_factors_mult(0, []) :- !.
prime_factors_mult(1, []) :- !.
prime_factors_mult(X, [X]) :- is_prime(X), !.
prime_factors_mult(X, Out) :-
  prime_factors_mult_t(X, 2, 0, [], Out), !.

prime_factors_mult_t(1, _, _, Out, Out).
prime_factors_mult_t(X, X, CurrentPower, CurrentFactors, Out) :-
  Power is CurrentPower + 1,
  append(CurrentFactors, [[X, Power]], Out).

prime_factors_mult_t(X, TestFactor, Power, CurrentFactors, Out) :-
  gcd(X, TestFactor, GCD),
  GCD \== 1, !,
  NewPower is Power + 1,
  Z is X / TestFactor,
  prime_factors_mult_t(Z, TestFactor, NewPower, CurrentFactors, Out).

prime_factors_mult_t(X, TestFactor, Power, CurrentFactors, Out) :-
  Power >= 1,
  append(CurrentFactors, [[TestFactor, Power]], NewFactors),
  NewTestFactor is TestFactor + 1,
  prime_factors_mult_t(X, NewTestFactor, 0, NewFactors, Out).

prime_factors_mult_t(X, TestFactor, Power, CurrentFactors, Out) :-
  Power = 0,
  NewTestFactor is TestFactor + 1,
  prime_factors_mult_t(X, NewTestFactor, 0, CurrentFactors, Out).

Essentially, prime_factors_mult performs the same steps as prime_factors. However, instead of creating a list for some prime factor right from the beginning, the power of that prime factor is accumulated and stored at last.

Happy, Prolog-ing and if you find any errors/typos please report them.