Search code examples
numbersprologdivider

Prolog: dividing a number


I wanted to make a predicate that returns a list of a number dividers. Example: 72 = 2*2*2*3*3.

prdel(A,[],_):- 
      A is 1.
prdel(P,[D|L],D):-
      0 is mod(P,D),
      P1 is P/D,
      prdel(P1,L,D).
prdel(P,L,D):-
      D1 is D+1,
      prdel(P,L,D1).

This works and returns the right list. The problem is that it does not stop after that but returns the same list over and over again if I press space (I am sorry I don't know the term in English when you use the same predicate to get different answer). I want it to stop after the first time.

I tried to edit the last one like that,

prdel(P,L,D):-
      D1 is D+1,
      D1<P,
      prdel(P,L,D1).

but now it returns only false and not the list.

EDIT:

I am looking for an answer without cut.


Solution

  • One problem in your code is that it keeps trying to divide the number P by D even when it is clear that the division is not going to succeed because D is too high. This lets D "run away" without a limit.

    Adding a check for D1 to be below or equal to P fixes this problem:

    prdel(1,[],_).
    
    prdel(P,[D|L],D):-
          0 is mod(P,D),
          P1 is P/D,
          prdel(P1,L,D).
    
    prdel(P,L,D):-
          D1 is D+1,
          D1 =< P,
          prdel(P,L,D1).
    

    This produces all combinations of divisors, including non-prime ones (demo).

    [[2, 2, 2, 3, 3], [2, 2, 2, 9], [2, 2, 3, 6],
     [2, 2, 18], [2, 3, 3, 4], [2, 3, 12], [2, 4, 9],
     [2, 6, 6], [2, 36], [3, 3, 8], [3, 4, 6], [3, 24],
     [4, 18], [6, 12], [8, 9], [72]]
    

    If you do not want that, add the condition that mod(P,D) > 0 in the last clause:

    prdel(1,[],_).
    
    prdel(P,[D|L],D):-
        0 is mod(P,D),
        P1 is P/D,
        prdel(P1,L,D).
    
    prdel(P,L,D):-
        mod(P,D) > 0,
        D1 is D+1,
        D1 =< P,
        prdel(P,L,D1).
    

    This produces only [2, 2, 2, 3, 3] (demo).