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只有一个结果。

一个可行的解决方案是：

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（一个名为 的谓词primeNumber，有一个参数）是一个完全独立于primeNumber/2（同名，两个参数）的谓词。仅获得起始值的额外参数的“子函数”通常具有相同的名称。因此，prime_prime您不应该只使用primeNumber，尽管在 Prolog 中您通常不使用 camelCase。

使用 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 中，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 时，第一条规则期望一个不可能的数学条件（请记住，Prolog 中的逗号[,] 是一个连词）
  • 规则以 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).

除了他使用 Prolog if-then-else 结构外，这个逻辑与 Kay 的基本相同。

于 2014-09-22T14:15:37.727 回答