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.

Answer 3

X mod Y is 0 always fails, because no expressions allowed on the left of is.

Change to 0 is X mod Y, or, better, to X mod Y =:= 0

Answer 4

agarwaen's accepted answer does not perform well on large numbers. This is because it is not tail recursive (I think). Also, you can speed everything up with a few facts about prime numbers.

1) 2 is the only even prime number

2) Any number greater than half the original does not divide evenly

isPrime1(2) :-
    !.
isPrime1(3) :-
    !.
isPrime1(X) :-
    X > 3,
    (  0 is X mod 2 
    -> false
    ;  Half is X/2,
       isPrime1_(X,3,Half)
    ).

isPrime1_(X,N,Half) :-
    (  N > Half 
    -> true
    ;  0 is X mod N
    -> false
    ;  M is N + 2,
       isPrime1_(X,M,Half)
    ).

1 ?- time(isPrime1(999983)). % 1,249,983 inferences, 0.031 CPU in 0.039 seconds (80% CPU, 39999456 Lips) true.

EDIT1

Is it possible to take it a step further? isPrime_/3 is more efficient than isPrime2/1 because it compares only to previously known primes. However, the problem is generating this list.

allPrimes(Max,Y) :- 
    allPrimes(3,Max,[2],Y).

allPrimes(X,Max,L,Y) :-
    Z is X+2,
    N_max is ceiling(sqrt(X)),
    (  X >= Max 
    -> Y = L;
    (  isPrime_(X,L,N_max)
    -> append(L,[X],K),       %major bottleneck
       allPrimes(Z,Max,K,Y)
    ;  allPrimes(Z,Max,L,Y)
    )).

isPrime_(_,[],_).

isPrime_(X,[P|Ps],N_max) :-
    (  P > N_max  
    -> true     %could append here but still slow
    ;  0 =\= X mod P,
       isPrime_(X,Ps,N_max)
    ).

Answer 5

I thing that is elegant way:

isPrime(A):-not((A1 is A-1,between(2,A1,N), 0 is mod(A,N))),not(A is 1).

1 IS NOT PRIME NUMBER, but if you don't think so just delete not(A is 1).

Answer 6

Was trying something else. A pseudo primality test based on Fermats little theorem:

test(P) :- 2^P mod P =:= 2.

test2(P) :- modpow(2,P,P,2).

modpow(B, 1, _, R) :- !, R = B.
modpow(B, E, M, R) :- E mod 2 =:= 1, !,
   F is E//2,
   modpow(B, F, M, H),
   R is (H^2*B) mod M.
modpow(B, E, M, R) :- F is E//2,
   modpow(B, F, M, H),
   R is (H^2) mod M.

Without the predicate modpow/4 things get too slow or integer overflow:

?- time(test(99999989)).
% 3 inferences, 0.016 CPU in 0.016 seconds (100% CPU, 192 Lips)
true.

?- time(test2(99999989)).
% 107 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
true.

?- time(test(99999999999900000001)).
% 4 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 190476 Lips)
ERROR: Stack limit (1.0Gb) exceeded

?- time(test2(99999999999900000001)).
% 267 inferences, 0.000 CPU in 0.000 seconds (87% CPU, 1219178 Lips)
true.

Not yet sure how to extend it to a full primality test.

Answer 7

Using findall and between

is_prime(N) :- 
             HalfRange is round(N/2),
             % Iterate over all X values in [2, HalfRange] and if (N mod X) is 0 then put X in ModList list
             findall(X, (between(2, HalfRange, X), 0 is mod(N, X), !), ModList),
             % N is prime iff ModList is empty
             length(ModList, ModCount), ModCount =:= 0.