%Source: https://sites.google.com/site/prologsite/prolog-problems %query:prime_factors_mult(g,f). % 2.03 (**) 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]] next_factor(_,2,3) :- !. next_factor(N,F,NF) :- F * F < N, !, NF is F + 2. next_factor(N,_,N). % F > sqrt(N) % 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).
content may be truncated. 'popout' for larger text window.
