How to count nth prime in prolog

user_13269450 0
Viewed 164

I'm quite new to prolog and I am trying to write a predicate which gives the value of nth prime number and it looks like nth_prime(N, Prime) . I have already done the function that counts if the number is prime or not

div(X, Y):- 0 is X mod Y.
div(X, Y):- X>Y+1, Y1 is Y+1, div(X, Y1).

prime(2):- true.
prime(X):- X<2, false.
prime(X):- not(div(X, 2)).

I don't understand what is my next step, and how I should count which prime belong to N.

primes prolog
2 Answers

Your code is a bit unusual for prolog but (with the exception of prime(1)) it works.

Here is a solution for your predicate:

nextprime(N,N):- 
    prime(N),
    !.
nextprime(P, Prime):-
    PP is P+1,
    nextprime(PP,Prime).

nthprime(1, 2).
nthprime(N, Prime):-
    N>1,
    NN is N-1,
    nthprime(NN, PrevPrime),
    PP is PrevPrime+1,
    nextprime(PP, Prime).

?- nthprime(1,P).
P = 2 ;
false.

?- nthprime(2,P).
P = 3 ;
false.

?- nthprime(3,P).
P = 5 ;
false.

It works as follows: It is known that the first prime number is 2 (nthprime(1, 2).). For every other number N larger than 1, get the previous prime number (nthprime(NN, PrevPrime)), add 1 until you hit a prime number. The add 1 part is done through a help predicate nextprime/2: for a given number P it will check if this number is a prime. If yes, it returns this number, otherwise it will call itself for the next higher number (nextprime(PP,Prime)) and forwards the output. The bang ! is called a cut which cuts the other choice branches. So if you once hit a prime, you can not go back and try the other path.

To test it you can ask ?- nthprime(N,P). for a given N. Or to check multiple answers at once, let's introdice a helperpredicate nthprimeList/2 which calls nthprime/2 for every item in the firstlist and puts the "output" into a list:

nthprimeList([],[]).
nthprimeList([N|TN],[P|TP]):-
    nthprime(N,P),
    nthprimeList(TN,TP).

?- nthprimeList([1,2,3,4,5,6,7,8,9],[P1,P2,P3,P4,P5,P6,P7,P8,P9]).
P1 = 2,
P2 = 3,
P3 = 5,
P4 = 7,
P5 = 11,
P6 = 13,
P7 = 17,
P8 = 19,
P9 = 23;
false.
user_80806480

Using your definitions, we define the following to count up and test all numbers from 2 and up, one after another:

nth_prime(N, Prime):-
  nth_prime(N, Prime, 1, 2).  % 2 is the candidate for 1st prime

nth_prime(N, P, I, Q):-   % Q is I-th prime candidate
  prime(Q) 
  -> ( I = N, P = Q
     ; I1 is I+1, Q1 is Q+1, nth_prime(N, P, I1, Q1) 
     )
  ;  Q1 is Q+1, nth_prime(N, P, I, Q1).

Testing:

30 ?- nth_prime(N,P).
N = 1,
P = 2 ;
N = 2,
P = 3 ;
N = 3,
P = 5 ;
N = 4,
P = 7 ;
N = 5,
P = 11 .

31 ?- nth_prime(N,P), N>24.
N = 25,
P = 97 ;
N = 26,
P = 101 ;
N = 27,
P = 103 .

32 ?- nth_prime(N,P), N>99.
N = 100,
P = 541 ;
N = 101,
P = 547 ;
N = 102,
P = 557 .
user_8498910
Related