Prime factorization in prolog

Question

I'm new to Prolog. I read this code which finds prime factors of an integer:

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), !.

And changed it to this one:

factors(1,[[1,1]]) :-
   true, !.
factors(X,[Factor1|T]) :-
   X > 0,
   (  is_list(Factor1),
      length(Factor1, 2),
      Factor1 = [Base|A],
      A = [Pow], 
      between(2,X,Base),
      between(1,100,Pow), 
      NewX is X / (Base ** Pow),
      (X mod Base) =:= 0,
      (NewX mod Base) =\= 0
   ),
   factors(NewX,T), !.

Well the first one works perfect, but the latter doesn't respond to queries. i.e. when I enter:

factors(2,[[2,1],[1,1]]).  

I get 'true', but when I enter:

factors(2,X).  

I get 'false'.

Answer 1

Because Base and Pow aren't bound to anything yet (they are parts of the X that you pass), you can't compute NewX (and the betweens might not work, either).

Answer 2

When you enter factors(2,X), Factor1 is not bound and is_list(Factor1) fails.

I think your code

is_list(Factor1),
length(Factor1, 2),
Factor1 = [Base|A],
A = [Pow]

can be abbreviated to Factor1 = [Base,Pow]. Since Factor1 is not used anywhere else, you can move [Base,Pow] into the head of the clause.

You can omit true, it has no effect here. The parenthesis haven't any effect, neither. So your code could be written as:

factors(1,[[1,1]]) :- !.
factors(X,[[Base,Pow]|T]) :-
   X > 0,
   between(2,X,Base),
   between(1,100,Pow), 
   NewX is X / (Base ** Pow),
   (X mod Base) =:= 0,
   (NewX mod Base) =\= 0,
   factors(NewX,T), !.

On my system (using SICStus), one must use

NewX is X // floor(Base ** Pow)

to prevent that NewX becomes a float which leads to an error when passed to mod as argument.

Edit: I originally wrote that the last cut had no effect. That is not true because between/2 creates choice points. I removed that part of my answer and put the cut back into the code.