% P36 (**) Determine the prime factors of a given positive integer (2).
% Construct a list containing the prime factors and their multiplicity.
% Example:
% ?- prime_factors_mult(315, L).
% L = [[3,2],[5,1],[7,1]]
:- ensure_loaded(p35). % make sure next_factor/3 is loaded
% prime_factors_mult(N, L) :- L is the list of prime factors of N. It is
% composed of terms [F,M] where F is a prime factor and M its multiplicity.
% (integer,list) (+,?)
prime_factors_mult(N,L) :- N > 0, prime_factors_mult(N,L,2).
% prime_factors_mult(N,L,K) :- L is the list of prime factors of N. It is
% known that N does not have any prime factors less than K.
prime_factors_mult(1,[],_) :- !.
prime_factors_mult(N,[[F,M]|L],F) :- divide(N,F,M,R), !, % F divides N
next_factor(R,F,NF), prime_factors_mult(R,L,NF).
prime_factors_mult(N,L,F) :- !, % F does not divide N
next_factor(N,F,NF), prime_factors_mult(N,L,NF).
% divide(N,F,M,R) :- N = R * F**M, M >= 1, and F is not a factor of R.
% (integer,integer,integer,integer) (+,+,-,-)
divide(N,F,M,R) :- divi(N,F,M,R,0), M > 0.
divi(N,F,M,R,K) :- S is N // F, N =:= S * F, !, % F divides N
K1 is K + 1, divi(S,F,M,R,K1).
divi(N,_,M,N,M).