CODEWITHSUNDEEP
prolog
mirosoft
mirosoft

Reputation: 305

Strawberry Prolog - recursive issue

I am new to Prolog and I have an issue using this code of finding if a number is prime.

finddivs(N,L) :- helpdivs(N,1,L).

helpdivs(N,I,L) :- I > N. 
helpdivs(N,I,[Lm|Lk]) :- 
  N mod I =:= 0,   
  Lm is I, Ii is I + 1, 
  helpdivs(N,Ii,Lk). 
helpdivs(N,I,L) :- Ii is I+1, helpdivs(N,Ii,L).

takefirst([M|_],M).

length([],0). 
length([_|Lrst],N) :- length(Lrst,N1), N is N1+1.

is_prime(N) :- finddivs(N,L), write(L), nl,
               length(L,P), write(P), nl, P =:= 2.

is_primeh(2).

?- is_prime(4), nl.

The result is:

.....
3
[1, 2, 4]
3
[1, 2, 4]
3
[1, 2, 4]
3
[1, 2, 4]The program is terminated.

I tried !,fail. at the end of the function, but still doesn't help.

Can you explain me why this happens?

Upvotes: 1

Views: 201

Answers (1)

lurker
lurker

Reputation: 58254

To codify this as an answer, the issue with the original implementation is that the predicate helpdivs permits Prolog to backtrack into other clauses regardless of the value of I.The following implementation will prevent Prolog from backtracking when you don't want it to by constraining the value of N in each case:

helpdivs(N, I, L) :-
    I > N. 
helpdivs(N, I, [Lm|Lk]) :-
    I =< N,
    N mod I =:= 0,   
    Lm is I, Ii is I + 1, 
    helpdivs(N,Ii,Lk). 
helpdivs(N, I, L) :-
    I =< N,
    N mod I =\= 0,
    Ii is I+1,
    helpdivs(N, Ii, L).

To make it a little more DRY, you can use the if-then-else:

helpdivs(N, I, _) :-
    I > N.
helpdivs(N, I, L) :-
    I =< N,
    Ii is I + 1,
    (   N mod I =:= 0
    ->  L = [I|Lk],
        helpdivs(N, Ii, Lk)
    ;   helpdivs(N, Ii, L)
    ).

There are probably other similar variations on this theme that would work as well.

Upvotes: 1

Related Questions