CODEWITHSUNDEEP
prologprimes
Vs_De_S
Vs_De_S

Reputation: 155

prolog list of all divisors of a number

I want to find all the divisors of a natural number.and output a list.

now my code looks like this:

divisors(0,[]).
divisors(N,[N1|P]):- 
    N1=N,
    RES is (N mod N1),
    N1 is N-1, 
    RES==0,
    divisors(N,P).
divisors(N,[N1|P]):- 
    N1=N,
    RES is (N mod N1),
    N1 is N-1, 
    RES\=0,!, fail.

but it doesn't work. tell me, what am I doing wrong? I've seen what can be done via findall, but I want to do it differently.The idea is as follows. Subtract one from the number (whose divisors we are looking for) each time and if the original number is divided by a new number, then write it to the head of the list.

(I just realized..That I don 't remember N anywhere ..since with recursive calls, it will already be different. I'm completely confused..)

Upvotes: 1

Views: 130

Answers (2)

Will Ness
Will Ness

Reputation: 71074

(I just realized..That I don 't remember N anywhere ..since with recursive calls, it will already be different. I'm completely confused..)

That's right, there is no concept of nested scope in Prolog. Instead, we pass everything we need further down among the predicate's arguments, possibly using additional arguments.

Minimal edit to fix your code:

divisors(N,L):- divisors(N,N,L).

divisors(N,0,[]):- !.
divisors(N,N1,[N1|P]):-    % use N1
    %N1=N,
    RES is (N mod N1),
    N2 is N1-1, 
    RES==0,
    divisors(N,N2,P).      
divisors(N,N1,P):-         % skip N1
    %N1=N,
    RES is (N mod N1),
    N2 is N1-1, 
    RES\=0, %!, fail
    divisors(N,N2,P).      % same P

The result list L is instantiated in the top-down fashion.

Examples:

49 ?- divisors(12,L).
L = [12, 6, 4, 3, 2, 1].

50 ?- divisors(37,L).
L = [37, 1].

Upvotes: 1

Nicholas Carey
Nicholas Carey

Reputation: 74297

The brute force way of finding all the divisors of a natural number would be something like this:

divisors( 0 , []  ) .  % zero is a special case
divisors( N , Ds  ) :- % otherwise, the general case applies
  integer(N),          % - N must be an integer, and
  N > 0,               % - N must be positive (and greater than 0)
  divisors(1,N,Ds)     % - invoke our helper predicate to try all possible divisors from 1–N inclusive
  .                    % - Easy!

divisors( D , N , [D|Ds] ) :- % case 1: D is a divisor of N
  D < N ,                     %   - D must be less than N, and
  0 =:= N mod D,              %   - D must be an integer divisor of N,
  !,                          %   - eliminate the choice point
  D1 is D+1,                  %   - increment D
  divisors(D1,N,Ds)           %   - recurse down, with D prepended to the result list
  .                           %
divisors( D , N ,    Ds  ) :- % case 2: D is not a divisor of N
  D < N ,                     %   - D must be less than N, and
  0 =\= N mod D,              %   - D must not be an integer divisor of N
  !,                          %   - eliminate the choice point
  D1 is D+1,                  %   - increment D
  divisors(D1,N,Ds) .         %   - recurse down, discarding the current D
divisors( N , N , [N]    )    % case 3: every number is its own divisor.
  .                           %

Upvotes: 1

Related Questions