How can I create a list of factors of a number?-CodePudding

I want to create a function factoring that takes a number and returns a list of all of its factors in ascending order. My current issue is that some factors repeat themselves and others do not show up at all

factors(X,121) returns [11,11,1] instead of just [11] factors(X,16) returns [2,2,2,1] instead of [2,4,8]

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

Expected behavior is for factors(A,16) to return the list [2,4,8].

1 and the target number are not included in the list. The 1 is already being handled in the first statement. I would like to use the most basic syntax possible so that I can become more familiar with how Prolog works.

CodePudding user response：

Using the trial division algorithm for factoring an integer N, the upper limit on what needs to be tried is the square root of N: consider a perfect square like 81. Its factors are:

1 x 81
3 x 27
9 x 9

And any values higher than sqrt(81) (9) are the quotient from integer division of 81 by a value less than or equal to 9.

So... factoring a number is easy:

factor(N,F) :-
    integer(N),
    N >= 0 ,
    L is floor(sqrt(N)) ,
    between(1,L,F1) ,
    div_rem(N,F1,F2,0) ,
    unique_factors(F1,F2,F)
    .
    
div_rem(X,Y,Q,R) :-
    Q is X div Y ,
    R is X mod Y
    .

unique_factors(A,B,A) :- A \= B .
unique_factors(_,B,B) .

To collect all the factors is even easier:

factors(N,Fs) :- findall(F, factor(N,F), F0), sort(F0,Fs).

One should note here, that that sort/2 removes duplicates and turns the unsorted list into, strictly speaking, an ordered set. See it in the playground: https://swish.swi-prolog.org/p/QuUnomwk.pl

If you want to remove 1 and N from the list of factors, simply change

between(1,L,F1)

between(2,L,F1)

CodePudding user response：

One problem is that you are mixing up backtracking and recursion. With this code:

test(X) :-
    between(2, 5, X).

?- test(Answer).
Answer = 2 ;
Answer = 3 ;
Answer = 4 ;
Answer = 5

The code finds one value for X between 2 and 5 and leaves a choicepoint; then when I use ; to ask it to find another, Prolog backtracks to the choicepoint and finds the next value between 2 and 5.

With your code, you are using between(2,B,X) which generates values on backtracking, and at the same time you are doing I is B // X to make a new endpoint and then descending into factors(T, I) which starts between() from 2 again. And you cut ! to discard choicepoints, so backtracking can never come back to find the rest of the numbers up to the earlier B, either. That's where your [2, 2, 2 is coming from, I think.

You can do it either way, as Nicholas Carey answers with between() and then using findall to generate all the backtracking answers. Or by using recursion:

n_factors(N, F) :-
    n_factors(N, 1, F).

n_factors(Num, Num, [1]).  % Base case.

n_factors(Num, Counter, [H|T]) :- % Case where Counter is a factor
    0 =:= Num mod Counter,
    H is Num div Counter,
    succ(Counter, Cnext),
    n_factors(Num, Cnext, T).

n_factors(Num, Counter, T) :- % Case where Counter is NOT a factor
    0 =\= Num mod Counter,
    succ(Counter, Cnext),
    n_factors(Num, Cnext, T).

e.g.

?- time(n_factors(121, Factors)).
482 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 1852400 Lips)
Factors = [121, 11, 1]

?- time(n_factors(1048576, F)).
4,194,302 inferences, 0.785 CPU in 0.785 seconds (100% CPU, 5344086 Lips)
F = [1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]

(You may want to compare time() and see just how much quicker it is to do stop counting at the square root of N, as the other answer does).

Or rewrite your approach to