3

入力が素数であるかどうかを計算しようとしていますが、何か問題が発生しています...これが私のコードです:

primeNumber(X):-
    prime_prime(A, 1).

prime_prime(A, B):-
    R is A mod B,
    R =:= 1,
    R =:= A.
prime_prime(X, B):-
    B < A,
    Next is B + 1,
    prime_prime(A, Next).

false毎回与えてくれます。私が間違っていることについて何か手がかりやアイデアを得た人はいますか?

4

2 に答える 2

4

http://www.swi-prolog.org/pldoc/man?function=mod/2を参照してください:

+IntExpr1 mod +IntExpr2
Result = IntExpr1 - (IntExpr1 div IntExpr2) × IntExpr2 として定義されるモジュロ。ここで、div は床除算です。

そうRあるべきです0。modの結果は 1 つだけです。

実用的な解決策は次のとおりです。

primeNumber(A) :-
    A > 1,                 % Negative numbers, 0 and 1 are not prime.
    prime_prime(A, 2).     % Begin iteration:

prime_prime(A, B) :-       % Test if A divides by B without remainder
    B >= A                 % The limit was reached?
    ->  true               %     Then it's prime.
    ;   0 is A mod B       % B divides A without a remainder?
    ->  false              %     Then it's not prime.
    ;   succ(B, C),        % Otherwise: C is B + 1
        prime_prime(A, C). % Test if C divides A.

ちなみに、primeNumber/1(a predicate named , with one argument) は、 (same name, two arguments)primeNumberとはまったく別の述語です。primeNumber/2開始値の追加の引数のみを取得する「サブ関数」には、通常、同じ名前が付けられます。そのため、代わりにprime_primeを使用する必要がありますprimeNumberが、Prolog では通常キャメルケースを使用しません。

Sergei Lodyagin がコメントで提案した最適化を使用します。

primeNumber(A) :-
    A > 1,                    % Negative numbers, 0 and 1 are not prime.
    sqrt(A, L),               % A prime factor of A is =< the square root of A.
    prime_prime(A, 2, L).     % Begin iteration:

prime_prime(A, B, L) :-       % Test if A divides by B without remainder
    B >= L                    % The limit was reached?
    ->  true                  %     Then it's prime.
    ;   0 is A mod B          % B divides A without a remainder?
    ->  false                 %     Then it's not prime.
    ;   succ(B, C),           % Otherwise: C is B + 1
        prime_prime(A, C, L). % Test if C divides A.

また、定義済みの述語を使用する場合between(+Low, +High, ?Value):

primeNumber(A) :-
    L is floor(sqrt(A)),
    \+ (between(2, L, X),
        0 is A mod X).

さらに反復回数を減らすには、奇数モジュールをテストするだけで済みます。

primeNumber(2).
primeNumber(A) :-
    A > 2,
    \+ 0 is A mod 2,
    L is floor(sqrt(A) / 2),
    \+ (between(1, L, X),
        0 is A mod (1 + 2*X)).
于 2014-09-22T11:08:32.690 に答える
2

Kay は、壊れたプログラムの動作する修正を既に提供しています。何が壊れているのかを簡単に分析します。

Prolog で問題を解決するときは、最初に何が必要かを論理的に書き出せるとよいでしょう。この場合、次のように宣言する必要があるようです。

A number, A, is prime if, for each number B < A, the value of A mod B is non-zero.

これを Prolog に直接レンダリングする方法はおそらくいくつかありますが、そのうちの 1 つを Kay が示しています。

ただし、元のルールの記述方法は、次のように述べています。

A number, A, is prime if:
    (Rule 1) The value of A mod B, for a given value of B, is 1 and is also A.
 OR (Rule 2) B < A and Rule 1 is satisfied with A and B+1.

ご覧のとおり、定義されたルールにはいくつかの問題があります。

  • この規則は、元の数値とそれよりも小さいすべての数値との間のモジュロ関係に関して記述された素数の論理的定義と一致しません。
  • 最初のルールは、A が 1 に等しくない場合、不可能な数学的条件を予期します (プロローグのコンマ[,] は接続詞であることを思い出してください) 。
  • ルールは 1 の開始除数で開始されます。1 はすべてを除算し、機能するルールの例外になる可能性があるため、これはおそらく悪いことです。

編集

モジュロ演算子を使用した素数の最初の定義に戻ると、次のように Prolog に変換できます。

is_prime(N) :-                 % N is prime if...
  N > 1,                       % N > 1, and
  non_divisible_from(N, 2).    % N is non-divisible by everything from 2 to N-1

non_divisible_from(N, D) :-    % N is non-divisible by D through N-1 if...
  N =< D.                      % D >= N
                               % --OR--
non_divisible_from(N, D) :-    % N is non-divisible from D to N-1 if...
  N > D,                       % N > D, and
  N mod D =\= 0,               % N is non-divisible by D, and
  D1 is D + 1,                 % N is non-divisible by D+1 to N-1
  non_divisible_from(N, D1).

このロジックは基本的に Kay のものと同じですが、彼は Prolog の if-then-else 構造を使用しています。

于 2014-09-22T14:15:37.727 に答える