Comment compter le nième prime dans le prologue

Question

Je suis assez nouveau dans le prologue et j'essaye d'écrire un prédicat qui donne la valeur du nième nombre premier et cela ressemble à nth_prime(N, Prime) . J'ai déjà fait la fonction qui compte si le nombre est premier ou non

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

Je ne comprends pas quelle est ma prochaine étape et comment je devrais compter les premiers appartenant à N.

Answer 1

Votre code est un peu inhabituel pour le prologue mais (à l'exception de prime(1)) cela fonctionne.

Voici une solution pour votre prédicat:

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.

Cela fonctionne comme suit: On sait que le premier nombre premier est 2 ( nthprime(1, 2).). Pour tout autre nombre Nsupérieur à 1, obtenez le nombre premier précédent ( nthprime(NN, PrevPrime)), ajoutez 1 jusqu'à ce que vous atteigniez un nombre premier. La partie add 1 se fait via un prédicat d'aide nextprime/2: pour un nombre donné, Pil vérifiera si ce nombre est un nombre premier. Si oui, il renvoie ce nombre, sinon il s'appellera pour le nombre supérieur suivant ( nextprime(PP,Prime)) et transmettra la sortie. Le bang !s'appelle une coupe qui coupe les autres branches de choix. Donc, si vous atteignez une fois une prime, vous ne pouvez pas revenir en arrière et essayer l'autre voie.

Pour le tester, vous pouvez demander ?- nthprime(N,P).un donné N. Ou pour vérifier plusieurs réponses à la fois, introduisons un helperpredicate nthprimeList/2qui appelle nthprime/2chaque élément de la première liste et met la "sortie" dans une liste:

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.

Answer 2

En utilisant vos définitions, nous définissons ce qui suit pour compter et tester tous les nombres de 2 et plus, l'un après l'autre:

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

Essai:

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 .