Prolog Program To Check If A Number Is Prime

问题:

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 :)

回答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.

回答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 crucial changes (highlighted below):

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

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

Let's query!

?- time(isPrime1(99999989)).
% 99,999,990 inferences, 5.082 CPU in 5.078 seconds (100% CPU, 19678881 Lips)
true.

?- time(isPrime2(99999989)).
% 20,002 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 13615185 Lips)
true.

回答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

回答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)
    ).

回答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).