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 between
s might not work, either).
Prime factorization in prolog
-
22-07-2023 - |
Вопрос
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'.
Решение
Другие советы
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.