프롤로그에서 n 번째 소수를 계산하는 방법

Nov 24 2020

나는 프롤로그를 처음 접했고 n 번째 소수의 값을 제공하는 술어를 작성하려고 노력하고 있습니다 nth_prime(N, Prime) . 나는 이미 숫자가 소수인지 아닌지를 계산하는 기능을 수행했습니다.

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

내 다음 단계가 무엇인지, 어떤 소수가 N에 속하는지 어떻게 계산해야하는지 이해하지 못합니다.

답변

DuDa Nov 24 2020 at 18:33

귀하의 코드는 프롤로그에 대해 약간 이례적이지만 (예외를 제외하고 prime(1)) 작동합니다.

다음은 술어에 대한 솔루션입니다.

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.

다음과 같이 작동합니다. 첫 번째 소수는 2 ( nthprime(1, 2).) 로 알려져 있습니다. N보다 큰 다른 모든 숫자에 1대해 이전 소수 ( nthprime(NN, PrevPrime))를 구하고 소수에 도달 할 때까지 1을 더합니다. add 1 부분은 help 술어를 통해 수행됩니다. nextprime/2주어진 숫자에 P대해이 숫자가 소수인지 확인합니다. 그렇다면이 숫자를 반환하고 그렇지 않으면 다음으로 높은 숫자 ( nextprime(PP,Prime)) 를 호출 하고 출력을 전달합니다. 강타 !는 다른 선택 가지를 자르는 절단이라고합니다. 따라서 한 번 프라임에 도달하면 돌아가서 다른 경로를 시도 할 수 없습니다.

그것을 테스트하기 ?- nthprime(N,P).위해 당신은 주어진 N. 또는 한 번에 여러 답변을 확인하려면 firstlist의 모든 항목 nthprimeList/2을 호출 nthprime/2하고 "출력"을 목록에 넣는 helperpredicate를 소개하겠습니다.

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.
WillNess Nov 26 2020 at 23:10

귀하의 정의를 사용하여 다음을 정의하여 2 이상부터 차례로 모든 숫자를 계산하고 테스트합니다.

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

테스트 :

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 .