CODEWITHSUNDEEP
prologprimesprimality-test
user3427168
user3427168

Reputation: 21

Determine if number is prime in Prolog

So I'm trying to determine if a number is prime using only one predicate. I don't really understand why every number is being declared false here.

is_prime(2).
is_prime(X) :-
    X > 2, %0 and 1 aren't primes, 2 is dealt with above
    1 is mod(X,2), %number is odd
    N is floor(X/2), %I want to only divide X from 1 to X/2
    forall( between(1,N,Z), mod(X,Z) > 0 ). %This should do X mod 1:X/2

Upvotes: 2

Views: 3019

Answers (2)

mat
mat

Reputation: 40768

A very straight-forward solution uses CLP(FD) constraints to express the desired properties.

We start with a simpler predicate, which is true iff the number is composite:

is_composite(N) :-
        N #= A*B,
        [A,B] ins 2..sup.

The exact usage details for CLP(FD) constraints differ slightly between Prolog systems. With at most small modifications, you will be able to run the above in all most widely used systems.

Done!

Because:

A prime number is an integer greater than 1 that is not composite.

Here are a few examples:

?- length([_,_|_], P), \+ is_composite(P).
P = 2 ;
P = 3 ;
P = 5 ;
P = 7 ;
P = 11 ;
P = 13 ;
P = 17 ;
P = 19 ;
P = 23 ;
P = 29 ;
etc.

In general, it is good practice to use CLP(FD) constraints when reasoning over integers in Prolog.

Upvotes: 2

hakank
hakank

Reputation: 6854

The reason your code don't work is the start value of between/3: It should start with 2 (not 1), since X mod 1 is always 0.

Upvotes: 2

Related Questions