-1

素数かそうでないかを判断する述語を書きたいです。私はブルート フォース O(sqrt(n)) アルゴリズムによってこれを行っています。

1) number が 2 の場合、true を返し、それ以上述語をチェックしません。

2) 数が偶数の場合、false を返し、述語のチェックをこれ以上行いません。

3) 数が偶数でない場合は、平方根までの数の約数を確認します。プログラムのこの部分に到達すると、数は偶数ではないため、3 から始まる奇数の約数をチェックするだけでよいことに注意してください。偶数はステップ 2 で除去されました。

4) 偶数の約数が見つかった場合は、false を返し、それ以外は何もチェックしません。

5) チェックしている除数が数値の平方根より大きい場合は、true を返します。除数は見つかりませんでした。述語チェックを行わないようにします。

ここに私が持っているコードがあります:

oddp(N) :- M is N mod 2, M = 1.

evenp(N) :- not(oddp(N)).

prime(2) :- !.

prime(X) :- X < 2, write_ln('case 1'), false, !.

prime(X) :- evenp(X), write_ln('case 2'), false, !.

prime(X) :- not(evenp(X)), write_ln('calling helper'), 
prime_helper(X,3).

prime_helper(X, Divisor) :- K is X mod Divisor, K = 0, 
write_ln('case 3'), false, !.

prime_helper(X, Divisor) :- Divisor > sqrt(X),
write_ln('case 4'), !.

prime_helper(X, Divisor) :- write_ln('case 5'), 
Temp is Divisor + 2, prime_helper(X,Temp).

しかし、私は問題に直面しています。たとえば、prime(1) をクエリするとします。プログラムはまだ除数をチェックしています。「！」を追加すると思いました 前の条件が true かどうかのチェックをプログラムが停止するようにします。プログラムがこれを行っている理由を誰か教えてもらえますか? 私はこれが初めてで、コードを単純化できることを知っていることに注意してください。ただし、ヒントをいただければ幸いです。

4

2 に答える 2

3

プログラムにはいくつかの問題があります。

  1. !/0への呼び出しの後にカット、、を書くことfalse/0は無意味であり、カットに到達することはありません。これら 2 つの呼び出しの順序を交換してみてください。
  2. 最初の節は次のように簡略化oddp(N) :- N mod 2 =:= 1.できます。この簡略化は他の節にも適用できます。
  3. 述語not/1は非推奨であると考えたほうがよいでしょう。代わりに書いてevenp(N) :- \+ oddp(N).ください。これ(\+)/1は、失敗として否定するための標準的な演算子/制御構造です。
于 2014-03-15T12:19:38.913 に答える