Wie man die n-te Primzahl im Prolog zählt

Question

Ich bin ziemlich neu im Prolog und ich versuche ein Prädikat zu schreiben, das den Wert der n-ten Primzahl angibt und wie es aussieht nth_prime(N, Prime) . Ich habe bereits die Funktion ausgeführt, die zählt, ob die Zahl eine Primzahl ist oder nicht

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

Ich verstehe nicht, was mein nächster Schritt ist und wie ich zählen soll, welche Primzahl zu N gehört.

Answer 1

Ihr Code ist für Prolog etwas ungewöhnlich prime(1), funktioniert aber (mit Ausnahme von ).

Hier ist eine Lösung für Ihr Prädikat:

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.

Es funktioniert wie folgt: Es ist bekannt, dass die erste Primzahl 2 ( nthprime(1, 2).) ist. Für jede andere Zahl, die Ngrößer als ist 1, erhalten Sie die vorherige Primzahl ( nthprime(NN, PrevPrime)) und addieren Sie 1, bis Sie eine Primzahl treffen. Das Hinzufügen von 1 Teil erfolgt über ein Hilfsprädikat nextprime/2: Für eine bestimmte Zahl Pwird geprüft, ob diese Zahl eine Primzahl ist. Wenn ja, gibt es diese Nummer zurück, andernfalls ruft es sich selbst für die nächsthöhere Nummer ( nextprime(PP,Prime)) auf und leitet die Ausgabe weiter. Der Knall !wird Schnitt genannt, der die anderen auserlesenen Zweige schneidet. Wenn Sie also einmal eine Primzahl erreicht haben, können Sie nicht zurückgehen und den anderen Weg ausprobieren.

Um es zu testen, können Sie ?- nthprime(N,P).nach einer bestimmten fragen N. Oder um mehrere Antworten gleichzeitig zu überprüfen, führen wir ein Hilfspredikat ein, nthprimeList/2das nthprime/2jedes Element in der ersten Liste aufruft und die "Ausgabe" in eine Liste einfügt :

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

Anhand Ihrer Definitionen definieren wir Folgendes, um alle Zahlen ab 2 nacheinander zu zählen und zu testen:

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

Testen:

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 .