CODEWITHSUNDEEP
prologprimes
Sid Jones
Sid Jones

Reputation: 59

Finding prime factors in Prolog

prime_factors(N, [_:_]) :- prime_factors(N, [_:_], 2).

prime_factors(N, [_:_], D) :- N mod D == 0,  N1 is N div D, 
                          prime_factors(N1, [_:D], D).

prime_factors(N, [_:_], D) :- N mod D =\= 0, D1 is D+1, prime_factors(N, [_:_], D1).

This is my proposed solution to find the prime factors of an input N.

When I try to run it I am getting an error about such a predicate/2 not existing - is my syntax somehow wrong with the extended predicate/3?

Upvotes: 2

Views: 2078

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476977

Using a second parameter that only seems to unify in the second case, does not seem to make much sense. Furthermore this is not the way you construct a list in Prolog anyway, since:

  1. the "cons" has syntax [H|T], so then it should be [_|_];
  2. by using underscores the predicates are not interested in the values, you each time pass other parameters; and
  3. in Prolog one typically does not construct lists with answers, typically backtracking is used. One can use findall/3 to later construct a list. This is usually better since that means that we can also query like prime_factor(1425, 3) to check if 3 is a prime factor of 1425.

We can thus construct a predicate that looks like:

prime_factor(N, D) :-
    find_prime_factor(N, 2, D).

find_prime_factor(N, D, D) :-
    0 is N mod D.
find_prime_factor(N, D, R) :-
    D < N,
    (0 is N mod D
    -> (N1 is N/D, find_prime_factor(N1, D, R))
    ;  (D1 is D + 1, find_prime_factor(N, D1, R))
    ).

For example:

?- prime_factor(1425, R).
R = 3 ;
R = 5 ;
R = 5 ;
R = 19 ;
false.

?- prime_factor(1724, R).
R = 2 ;
R = 2 ;
R = 431 ;
false.

If we want a list of all prime factors, we can use findall/3 for that:

prime_factors(N, L) :-
    findall(D, prime_factor(N, D), L).

For example:

?- prime_factors(1425, R).
R = [3, 5, 5, 19].

?- prime_factors(1724, R).
R = [2, 2, 431].

?- prime_factors(14, R).
R = [2, 7].

?- prime_factors(13, R).
R = [13].

Upvotes: 4

Related Questions