-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)。该程序仍在检查除数。我以为添加'！将使程序停止检查先前条件是否为真。有人可以告诉我为什么程序会这样做吗？请记住，我是新手，我知道代码可以简化。但是，任何提示将不胜感激！

4

2 回答 2

3

你的程序有几个问题：

  1. !/0在调用 to 之后写一个 cutfalse/0是没用的，因为永远不会到达 cut 。尝试交换这两个调用的顺序。
  2. 第一个子句可以简化为oddp(N) :- N mod 2 =:= 1.您也可以在其他子句中应用这种简化。
  3. 谓词not/1最好被认为已弃用。改写evenp(N) :- \+ oddp(N).。这(\+)/1是将否定视为失败的标准操作员/控制结构。
于 2014-03-15T12:19:38.913 回答
3

@Paulo 列举了导致程序运行不正常的关键问题以及一些好的提示。我将在这个特定程序上添加更多提示。

  • 在编写谓词时，重点应该放在真实的东西上。如果您的谓词正确定义了成功案例，那么您无需显式定义失败案例，因为默认情况下它们会失败。这意味着您的语句#2 和#4 不需要专门定义为子句。

  • 您使用了很多削减，这通常表明您的程序没有有效或正确地定义。

在编写谓词时，首先以逻辑语言形式说明目的是有帮助的（您在语句 1 到 5 中已经这样做了，但我将在此重新表述）：

如果一个数字是 2（你的陈述 #1），或者它是奇数并且它不能被 3 或更高的奇数除数整除（你的陈述 #3），那么它就是素数。如果我们在 Prolog 中写出来，我们会得到：

prime(X) :-                   % X is prime if...
    oddp(X),                  % X is odd, AND
    no_odd_divisors(X).       % X has no odd divisors
prime(2).                     % 2 is prime

如果 X 模块 2 的计算结果为 1，则数字 X 是奇数。

oddp(X) :- X mod 2 =:= 1.     % X is odd if X module 2 evaluates to 1

请注意，与其创建一个在我想要成功时基本上失败的助手，我将创建一个在我想要成功时成功的助手。no_odd_divisors如果 X 没有任何奇数除数 >= 3，则将成功。

如果一个数字 X 不能被 3 整除，并且如果它不能被任何数字 3+2k 整除，直到 sqrt(X)（你的陈述 #5），它就没有奇数除数。

no_odd_divisors(X) :-         % X has no odd divisors if...
    no_odd_divisors(X, 3).    % X has no odd divisors 3 or above

no_odd_divisors(X, D) :-      % X has no odd divisors D or above if...
    D > sqrt(X), !.           % D is greater than sqrt(X)
no_odd_divisors(X, D) :-      % X has no odd divisors D or above if...
    X mod D =\= 0,            % X is not divisible by D, AND
    D1 is D + 2,              % X has no odd divisors D+2 or above
    no_odd_divisors(X, D1).

注意上面的一个切口。这表明当我们达到超过 sqrt(X) 时，我们已经做出了最终决定，我们不需要回溯到“noodod divisor”的其他选项（对应于，Do no more predicate checks. in your statement #5）。

这将产生以下行为：

| ?- prime(2).

yes
| ?- prime(3).

(1 ms) yes
| ?- prime(6).

(1 ms) no
| ?- prime(7).

yes
| ?-

请注意，我确实在prime(2)上面定义了第二个子句。在这种情况下，prime(2)将首先以 失败prime(X)，X = 2然后prime(2)在无处可退的情况下成功。如果我首先定义prime(2)，作为您的第一条语句（如果数字为 2，则返回 true 并且不再检查任何谓词。）表示：

prime(2).                     % 2 is prime
prime(X) :-                   % X is prime if...
    oddp(X),                  % X is odd, AND
    no_odd_divisors(X).       % X has no odd divisors

然后你会看到：

| ?- prime(2).

true ? a

no
| ?-

这将是完全有效的，因为 Prolog 首先成功了prime(2)，然后知道还有另一个子句要回溯到努力寻找其他方法来取得prime(2)成功。然后它在第二次尝试时失败并返回“否”。这个“不”有时会让 Prolog 新手感到困惑。prime(2)无论条款顺序如何，您还可以通过将条款定义为：

prime(2) :- !.

您选择哪种方法最终取决于您的谓词关系的目的。使用削减的危险在于，您可能会无意中阻止您可能真正想要的替代解决方案。所以它应该非常周到地使用，而不是作为减少输出的快速补丁。

于 2014-03-15T13:53:42.470 回答