@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.