searching for all divisors of a natural number

Scharfi

unread,

Mar 21, 2003, 1:51:48 PM3/21/03

to

Hello I am not very good in programming Prolog
can anyone help me to find the solution for my problem?
I am searching for all divisors of a natural number. The Results shall be in a list.

btw. don't care about my bad bad english...

Nick Wedd

unread,

Mar 24, 2003, 6:12:24 AM3/24/03

to

In message <31a909fd.03032...@posting.google.com>, Scharfi
<scharfi...@web.de> writes

Divide the problem into two steps:

Step 1.
Write a predicate divides(P,Q) which succeeds if P is a divisor of Q.

Step 2.
Call this predicate, and arrange to collect all the results into a list.

Nick
--
Nick Wedd ni...@maproom.co.uk

Ray Reeves

unread,

Mar 24, 2003, 5:48:30 PM3/24/03

to

Try primeFactors/2 in Amzi Prolog.

Ray Reeves

"Nick Wedd" <ni...@maproom.co.uk> wrote in message
news:4tuYnuEY...@maproom.demon.co.uk...

Scharfi

unread,

Mar 25, 2003, 10:46:30 AM3/25/03

to

> > Divide the problem into two steps:
> >
> > Step 1.
> > Write a predicate divides(P,Q) which succeeds if P is a divisor of Q.
> >
> > Step 2.
> > Call this predicate, and arrange to collect all the results into a list.

I've done this:

Program in Prolog:

isteiler(_,1).
isteiler(N,X) :- 0 is N mod X, X < N, X > 0.

teilerliste(_,1,[]).
teilerliste(N,Lauf,[Lauf|Liste]) :- isteiler(N,Lauf), Lauf1 is Lauf-1,
teilerliste(N,Lauf1,Liste).
teilerliste(N,Lauf,Liste) :- Lauf1 is Lauf-1,
teilerliste(N,Lauf1,Liste).

teiler(N,Liste) :- teilerliste(N, N / 2 + 1, Liste).

Programcall:

?- teiler(300,Liste).
Liste = [150, 100, 75, 60, 50, 30, 25, 20, 15|...]
Yes
?-

my problem is, that this Program puts out the list in the wrong order.
it should be: Liste = [2, 3, 5, 6, 10, 12, 15, 20, 25, 30, 50, 60, 75,
100, 150]
___________________________________________

isteiler(_,1).
isteiler(N,X) :- 0 is N mod X, X < N, X > 0.

teilerliste(_,N,[]).
teilerliste(N,Lauf,[Lauf|Liste]) :- isteiler(N,Lauf), Lauf1 is Lauf+1,
teilerliste(N,Lauf1,Liste).
teilerliste(N,Lauf,Liste) :- Lauf1 is Lauf+1,
teilerliste(N,Lauf1,Liste).

teiler(N,Liste) :- teilerliste(N, 1, Liste).

this don't run, because prolog don't accecpt N in row 4.
if I use teilerliste(_,999999999,[]). it works, but this is no correct
solution!

btw: "Teiler" is German and means "divisor".
"Liste" means "list"
"Lauf" means run or step

Nick Wedd

unread,

Mar 26, 2003, 4:18:47 AM3/26/03

to

In message <31a909fd.03032...@posting.google.com>, Scharfi
<scharfi...@web.de> writes

>Program in Prolog:

>
>isteiler(_,1).
>isteiler(N,X) :- 0 is N mod X, X < N, X > 0.

It would be better to verify X < N, X > 0 _before_ attempting the
calculation. For instance, if X is 0, you want to fail before trying to
divide by 0.

You have replaced teilerliste(_,1,[]) by teilerliste(_,N,[]).

teilerliste(_,1,[]) says that "the teilerlist of anything, starting at
1, is empty". This works. Your recursion terminates when you get to 1.

teilerliste(_,N,[]) says that "the teilerlist of anything, starting at
anything, is empty". But you need to get it to terminate _only_ when
you have finished, something like
teilerliste( X, N, [] ) :- [ some sum involving N and X ].

Bastian Dittmar

unread,

Mar 26, 2003, 4:36:37 AM3/26/03

to

Hi,
someone else in a Forum had the same question a few days ago,. I will just
paste my answer from there so if urs still dont work just try this one

dividers(Number,List) :- dv(number,1,List).
dv(Number,Number,[Number]).
dv(Number,Akk,[Akk|Tail]) :-
Number > Akk,
0 is NUmber mod Akk,
AkkNew is Akk+1,
dv(Number,AkkNew,Tail).
dv(Number,Akk,List) :-
Number > Akk,
not(0 is Number mod Akk).
AkkNew is Akk+1,
dv(Number,AkkNew,List).

u use it by typing dividers(10,X).
and it will return X=[1,2,5,10]