プロローグで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の部分は、ヘルプ述語を介して実行されますnextprime/2。指定された数について、Pこの数が素数であるかどうかを確認します。はいの場合はこの番号を返し、そうでない場合は次に大きい番号（nextprime(PP,Prime)）を呼び出して出力を転送します。強打!は他の選択の枝を切るカットと呼ばれます。したがって、一度素数に達した場合、戻って別のパスを試すことはできません。
それをテストする?- nthprime(N,P).ために、あなたは与えられたを求めることができますN。または、一度に複数の回答を確認するために、firstlistのすべての項目nthprimeList/2を呼び出しnthprime/2、「出力」をリストに入れるヘルパー述語を導入しましょう。
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 .