prologprimality-test

Basic primality test predicate in Prolog


I am trying to create a predicate isPrime/1 that checks if a given number is prime or not. I have come up with the following code:

primeRec(_, 2).
primeRec(X, Y) :- Y > 2, X mod Y-1 > 0, primeRec(X, Y-1).

isPrime(2).
isPrime(X) :- X > 1, X mod 2 > 0, primeRec(X, X).

but it does not seem to work, and I have no idea why. I've found my code to follow the same idea as this one here, except that mine always returns false. for any ?- isPrime(X). with X bigger than 2, which obviously should not happen.


Solution

  • The problem is that you need to define another variable, say Y1, and unify it with the evaluation of Y-1, i.e., Y1 is Y - 1 and use Y1 instead of Y-1 in the second rule for primeRec/1. This because if you want to evaluate an arithmetic expression you need to use is.

    primeRec(X, Y) :- Y > 2, Y1 is Y - 1, X mod Y1 > 0, primeRec(X, Y1).