Primality Test

Help!
1

I’m using the latest stable release of SWI-Prolog. I’m trying to write a script to test primality of numbers in a range using Fermat’s Little Theorem. I have two problems.

I’m not sure the equality =/2 is the same as congruence in modular arithmetic or if I should be running a different operator.

The second issue is that it fails. For some reason the script returns false for ?-prime(7).

%  Primality Test
%
%
prime(N):-

    %Fermat's Little Theorem
    (A**N) = (mod(A,N)),

    %Search Space
    integer(A),integer(N),
    A > 1, A < 25,
    N > 1, N < 23,

    %Divisibility Constraints
    not(N/A),
    not(N=A),
    !,true.

number(A,N):- prime(N), integer(A),(integer(N)).

Any tips are appreciated!

2

You probably want to use the clpfd library. This gives you proper constraints over search domains.

your program fails on the first line:

(A**N) = (mod(A,N))

This is not setting up a constraint. This is asserting that the left hand side and the right hand side are the same terms, doing any unification to make that happen. Since these are clearly not the same, not even after variable renaming, this fails.

3

Is there a specific operation you recommend to capture congruence in modular arithmetic? That’s what that line is supposed to be. I had originally used =:= but it threw the error that a callable was expected.

4

#= is the one in clpfd. This will constrain the search domain to only those solutions that satisfy that expression. Whether that’s sufficient for what you’re trying to do I couldn’t say.

You’ll probably want the same for your other comparators too. #< etc.

5

Thank you, I’ll see how it goes.

6

I incorporated the module recommended and it runs without throwing any errors or exceptions, but it looks like it doesn’t want me to handle the composite integer the way I am. Here’s the updated script:

%  Primality Test
%
%

:-use_module(library(clpfd)).


prime(N):-

    %Fermat's Little Theorem
    (A^N) #= (A mod N),

    %Search Space
    integer(A),integer(N),
    A #> 1, A #< 25,
    N #> 1, N #< 23,

    %Divisibility Constraints
    (N / A) #> 1,
    (N#\=A),
    !,true.

number(A,N):- prime(N), integer(A),(integer(N)).

And the trace and steps:

primality test v1 trace
primality test v1 trace919×713 88.1 KB

7

so chatgpt actually came up with a decent script over small ranges. I think this might serve the purpose I need.

:- use_module(library(clpfd)).

% Predicate to check if a number N is prime
is_prime(N) :-
    N #> 1,
    \+ has_divisor(N, 2).

% Auxiliary predicate to check if there exists a divisor of N starting from D
has_divisor(N, D) :-
    D * D #=< N,  % Check divisors up to the square root of N
    N mod D #= 0.
has_divisor(N, D) :-
    D * D #=< N,
    D2 #= D + 1,
    has_divisor(N, D2).

% Predicate to find all prime numbers in a given range [Low, High]
prime_in_range(Low, High, Primes) :-
    findall(P, (between(Low, High, P), is_prime(P)), Primes).

% Example query: Find primes between 1 and 23
% ?- prime_in_range(1, 23, Primes).