Factors of a number

Question

So I am relatively new to Prolog, and while this problem is easy in many other languages I am having a lot of trouble with it. I want to generate a List of factors for a number N. I have already built a predicate that tells me if a number is a factor:

% A divides B
% A is a factor of B
divides(A,B) :- A =\= 0, (B mod A) =:= 0.

% special case where 1 // 2 would be 0
factors(1,[1]) :- !.

% general case
factors(N,L):- N > 0, factor_list(1, N, L).
factor_list(S,E,L) :- S =< E // 2, f_list(S,E,L).

f_list(S,E,[])    :- S > E // 2, !.
f_list(S,E,[S|T]) :- divides(S,E), !, S1 is S+1, f_list(S1, E, T).
f_list(S,E,L)     :- S1 is S+1, f_list(S1,E,L).

Any help would be appreciated.

EDIT

I pretty much changed my entire solution, but for some reason predicates like factors(9, [1]) return true, when I only want factors(9, [1,3]) to return true. Any thoughts?

Answer 1

Here's why factors(9,[1]) is true: the timing of attempted instantiations (that is to say, unifications) is off:

f_list(S,E,[])    :- S > E // 2, !.
f_list(S,E,[S|T]) :- divides(S,E), !, S1 is S+1, f_list(S1, E, T).
f_list(S,E,L)     :- S1 is S+1, f_list(S1,E,L).

%%  flist(1,9,[1]) -> (2nd clause) divides(1,9), S1 is 2, f_list(2,9,[]).
%%  flist(2,9,[])  -> (3rd clause) S1 is 3, f_list(3,9,[]).
%% ... 
%%  flist(5,9,[])  -> (1st clause) 5 > 9 // 2, !.

because you pre-specify [1], when it reaches 3 the tail is [] and the match with the 2nd clause is prevented by this, though it would succeed due to divides/2.

The solution is to move the unifications out of clauses' head into the body, and make them only at the appropriate time, not sooner:

f_list(S,E,L) :- S > E // 2, !, L=[].
f_list(S,E,L) :- divides(S,E), !, L=[S|T], S1 is S+1, f_list(S1, E, T).
f_list(S,E,L) :- S1 is S+1, f_list(S1,E,L).

The above usually is written with the if-else construct:

f_list(S,E,L) :- 
  ( S > E // 2   -> L=[]
  ; divides(S,E) -> L=[S|T], S1 is S+1, f_list(S1, E, T)
  ;                          S1 is S+1, f_list(S1, E, L)
  ).

Also you can simplify the main predicate as

%% is not defined for N =< 0
factors(N,L):- 
  (  N =:= 1 -> L=[1]
  ;  N >= 2  -> f_list(1,N,L) 
  ).

Answer 2

Personally, I use a somewhat simpler looking solution:

factors(1,[1]):- true, !.
factors(X,[Factor1|T]):- X > 0,
 between(2,X,Factor1), 
 NewX is X // Factor1, (X mod Factor1) =:= 0,
 factors(NewX,T), !.

This one only accepts an ordered list of the factors.

Answer 3

Here is a simple enumeration based procedure.

factors(M, [1 | L]):- factors(M, 2, L).
factors(M, X, L):- 
   residue(M, X, M1), 
   ((M==M1, L=L1); (M1 < M, L=[X|L1])),
   ((M1=1, L1=[]); (M1 > X, X1 is X+1, factors(M1, X1, L1))).

residue(M, X, M1):-
  ((M < X, M1=M);
   (M >=X, MX is M mod X, 
     (MX=0, MM is M/X, residue(MM, X, M1);
      MX > 0, M1=M))).