Why is this elementary Prolog predicate not stopping execution?

Question

I want to write a predicate that determines if a number is prime or not. I am doing this by a brute force O(sqrt(n)) algorithm:

1) If number is 2, return true and do not check any more predicates.

2) If the number is even, return false and do no more checking predicates.

3) If the number is not even, check the divisors of the number up to the square root. Note that we need only to check the odd divisors starting at 3 since if we get to this part of the program the number is not even. Evens were eliminated in step 2.

4) If we find an even divisor, return false and do not check anything else.

5) If the divisor we are checking is larger than the square root of the number, return true, we found no divisors. Do no more predicate checking.

Here is the code I have:

oddp(N) :- M is N mod 2, M = 1.

evenp(N) :- not(oddp(N)).

prime(2) :- !.

prime(X) :- X < 2, write_ln('case 1'), false, !.

prime(X) :- evenp(X), write_ln('case 2'), false, !.

prime(X) :- not(evenp(X)), write_ln('calling helper'), 
prime_helper(X,3).

prime_helper(X, Divisor) :- K is X mod Divisor, K = 0, 
write_ln('case 3'), false, !.

prime_helper(X, Divisor) :- Divisor > sqrt(X),
write_ln('case 4'), !.

prime_helper(X, Divisor) :- write_ln('case 5'), 
Temp is Divisor + 2, prime_helper(X,Temp).

I am running into problems though. For example, if I query prime(1). the program is still checking the divisors. I thought that adding '!' would make the program stop checking if the prior conditions were true. Can someone tell me why the program is doing this? Keep in mind I am new at this and I know the code can be simplified. However, any tips would be appreciated!

Answer 1

@Paulo cited the key issues with the program that cause it to behave improperly and a couple of good tips. I'll add a few more tips on this particular program.

• When writing a predicate, the focus should be on what's true. If your predicate properly defines successful cases, then you don't need to explicitly define the failure cases since they'll fail by default. This means your statements #2 and #4 don't need to be specifically defined as clauses.

• You're using a lot of cuts which is usually a sign that your program isn't defined efficiently or properly.

When writing the predicates, it's helpful to first state the purpose in logical language form (which you have done in your statements 1 through 5, but I'll rephrase here):

A number is prime if it is 2 (your statement #1), or if it is odd and it is not divisible by an odd divisor 3 or higher (your statement #3). If we write this out in Prolog, we get:

prime(X) :-                   % X is prime if...
    oddp(X),                  % X is odd, AND
    no_odd_divisors(X).       % X has no odd divisors
prime(2).                     % 2 is prime

A number X is odd if X module 2 evaluates to 1.

oddp(X) :- X mod 2 =:= 1.     % X is odd if X module 2 evaluates to 1

Note that rather than create a helper which essentially fails when I want success, I'm going to create a helper which succeeds when I want it to. no_odd_divisors will succeeds if X doesn't have any odd divisors >= 3.

A number X has no odd divisors if it is not divisible by 3, and if it's not divisible by any number 3+2k up to sqrt(X) (your statement #5).

no_odd_divisors(X) :-         % X has no odd divisors if...
    no_odd_divisors(X, 3).    % X has no odd divisors 3 or above

no_odd_divisors(X, D) :-      % X has no odd divisors D or above if...
    D > sqrt(X), !.           % D is greater than sqrt(X)
no_odd_divisors(X, D) :-      % X has no odd divisors D or above if...
    X mod D =\= 0,            % X is not divisible by D, AND
    D1 is D + 2,              % X has no odd divisors D+2 or above
    no_odd_divisors(X, D1).

Note the one cut above. This indicates that when we reach more than sqrt(X), we've made the final decision and we don't need to backtrack to other options for "no odd divisor" (corresponding to, Do no more predicate checking. in your statement #5).

This will yield the following behavior:

| ?- prime(2).

yes
| ?- prime(3).

(1 ms) yes
| ?- prime(6).

(1 ms) no
| ?- prime(7).

yes
| ?-

Note that I did define the prime(2) clause second above. In this case, prime(2) will first fail prime(X) with X = 2, then succeed prime(2) with nowhere else to backtrack. If I had defined prime(2) first, as your first statement (If number is 2, return true and do not check any more predicates.) indicates:

prime(2).                     % 2 is prime
prime(X) :-                   % X is prime if...
    oddp(X),                  % X is odd, AND
    no_odd_divisors(X).       % X has no odd divisors

Then you'd see:

| ?- prime(2).

true ? a

no
| ?-

This would be perfectly valid since Prolog first succeeded on prime(2), then knew there was another clause to backtrack to in an effort to find other ways to make prime(2) succeed. It then fails on that second attempt and returns "no". That "no" sometimes confuses Prolog newcomers. You could also prevent the backtrack on the prime(2) case, regardless of clause order, by defining the clause as:

prime(2) :- !.

Which method you choose depends ultimately on the purpose of your predicate relations. The danger in using cuts is that you might unintentionally prevent alternate solutions you may actually want. So it should be used very thoughtfully and not as a quick patch to reduce outputs.

Answer 2

There are several issues on your program:

1. Writing a cut, !/0, after a call to false/0 is useless and as the cut will never be reached. Try exchanging the order of these two calls.
2. The first clause can be simplified to oddp(N) :- N mod 2 =:= 1. You can also apply this simplification in other clauses.
3. The predicate not/1 is better considered deprecated. Write instead evenp(N) :- \+ oddp(N).. The (\+)/1 is the standard operator/control construct for negation as failure.