List of prime factors of a given number in prolog with basics

user_14886754 0
Viewed 100

I actually have task in school to find all prime factors of a given number and return them as a list, but I'm struggling a littlebit because I'm still new when it comes to prolog. Here is my code:

divisible(A, B) :-A mod B =:= 0, !.
divisible(A, B) :-A > B + 1, divisible(A, B + 1).
isPrime(2).
isPrime(A) :-not(divisible(A, 2)).

nextPrime(A, P) :-P is A + 1, isPrime(P),!.
nextPrime(A, P) :-A0 is A + 1,nextPrime(A0, P).

primeFactors(B,L):-primeFactors(B,L,2).

primeFactors(2,[2],_).
primeFactors(3,[3],_).
primeFactors(B,L,C):-B>3, C<B//2, B mod C =:= 0,add_tail(L,C,L1),B1 is B//C, primeFactors(B1,L1,C).
primeFactors(B,L,C):-B>3, C<B//2, nextPrime(C,C1),primeFactors(B,L,C1).

add_tail([],X,[X]).
add_tail([H|T],X,[H|L]):-add_tail(T,X,L).

Idea was to start with primeFactors/2, then from there to forward to primeFactors/3 where is C a prime divider, so it's easier for user to call it. B is given number, L is list that I want to return.

I should point out that isPrime, nextPrime and add_tail worked perfectly fine on their own.

I saw that there are some solutions for this problem on the internet but I still have only basic knowledge in prolog.

prime-factoring prolog
1 Answers

Using your predicates I would do it like this:

primeFactors(1,[],_).
primeFactors(B,[C|L],C):-
    B > 1, 
    C =< B, 
    0 is B mod C,
    B1 is B//C, 
    primeFactors(B1,L,C).
primeFactors(B,L,C):-
    B > 1, 
    C < B, 
    0 < B mod C,
    nextPrime(C,C1),
    primeFactors(B,L,C1).

The first line is the end case: if you reached B==1 you found all factors. In the other cases B has to be greater than 1. Then you have the two cases: either the current primenumber C is a factor of B (2nd case) or it is not (3rd case).
In the case C is a prime factor of B, C has to be smaller or equal to B. The equal part is important to reach the case for B==1. If so, divide B by C and move on with the new value. Also C has to be a part of the prime number list ([C|L] --> head/tail notation of lists).

If C is not a prime factor of B (3rd case), search for the next higher prime factor and move on.

Test:

?- primeFactors(120,L,2).
L = [2, 2, 2, 3, 5] ;
false.

?- primeFactors(7,L,2).
L = [7] ;
false.

?- primeFactors(14,L,2).
L = [2, 7] ;
false.
user_80806480
Related