Prolog Program To Check If A Number Is Prime

Question

I wrote the following program based on the logic that a prime number is only divisible by 1 and itself. So I just go through the process of dividing it to all numbers that are greater than one and less than itself, but I seem to have a problem since I get all entered numbers as true. Here's my code...

divisible(X,Y) :-
    Y < X,
    X mod Y is 0,
    Y1 is Y+1,
    divisible(X,Y1).

isprime(X) :-
    integer(X),
    X > 1,
    \+ divisible(X,2).

Thanks in advance :)

Answer 1

I'm a beginner in Prolog but managed to fix your problem.

divisible(X,Y) :- 0 is X mod Y, !.

divisible(X,Y) :- X > Y+1, divisible(X, Y+1).

isPrime(2) :- true,!.
isPrime(X) :- X < 2,!,false.
isPrime(X) :- not(divisible(X, 2)).

The main issue was the statement X mod Y is 0. Predicate is has two (left and right) arguments, but the left argument has to be a constant or a variable that is already unified at the moment that the predicate is executing. I just swapped these values. The rest of the code is for checking number 2 (which is prime) and number less than 2 (that are not primes)

I forgot to mention that the comparison Y < X is buggy, because you want to test for all numbers between 2 and X-1, that comparison includes X.

Answer 2

This answer is a follow-up to @lefunction's previous answer.

isPrime2/1 is as close as possible to isPrime1/1 with a few changes (highlighted below):

isPrime2(2) :-
    !.
isPrime2(3) :-
    !.
isPrime2(X) :-
    X > 3,
    X mod 2 =\= 0,
    isPrime2_(X, 3).

isPrime2_(X, N) :-
    (  N*N > X
    -> true
    ;  X mod N =\= 0,
       M is N + 2,
       isPrime2_(X, M)
    ).
    

Let's query!

?- time(isPrime1(99999989)).
% 24,999,999 inferences, 3.900 CPU in 3.948 seconds (99% CPU, 6410011 Lips)
true.

?- time(isPrime2(99999989)).
% 5,003 inferences, 0.001 CPU in 0.001 seconds (89% CPU, 6447165 Lips)
true.