我想写一个谓词来确定一个数字是否是素数。我是通过蛮力O(sqrt(n))算法来完成的:
1)如果number为2，则返回true，不再检查任何谓词
2)如果数字是偶数，则返回false并且不再执行检查谓词。
3)如果这个数不是偶数，检查这个数的除数直到平方根。请注意,我们只需要检查从3开始的奇数因子因为如果我们得到这一部分程序中的数字不是偶数。偶数在步骤2中被淘汰。
4)如果找到偶数除数，则返回false，不检查其他任何内容。
5)如果我们要检查的除数大于这个数的平方根，返回真，没有除数。不再执行谓词检查。
下面是我的代码:
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)程序还在检查除数。我以为加上"!"，将使程序停止检查先前的条件是否为真。有人能告诉我为什么程序会这样做吗?请记住，我是新手，我知道代码可以简化。然而，任何提示将是感激的!
@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
注意，比起创建一个在我想要成功时失败的助手，我将创建一个在我想要它成功时成功的助手。如果X没有奇数因子>= 3,no_odd_divisors将成功。
如果一个数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)时，我们已经做出了最终决定，我们不需要回溯到"无奇数除数"的其他选项(对应于)。在你的声明#5)。
这将产生以下行为:
| ?- prime(2).
yes
| ?- prime(3).
(1 ms) yes
| ?- prime(6).
(1 ms) no
| ?- prime(7).
yes
| ?-
请注意，我确实在上面第二个定义了prime(2)子句。在这种情况下，prime(2)将首先与X = 2一起失败prime(X)，然后成功prime(2)，没有其他可回溯的地方。如果我首先定义了prime(2)，如您的第一个语句(如果number是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)成功。然后在第二次尝试时失败并返回"no"。这个"不"有时会让Prolog新手感到困惑。无论子句顺序如何，还可以通过将子句定义为:
prime(2)情况下的回溯:prime(2) :- !.
选择哪种方法最终取决于谓词关系的目的。使用切割的危险在于，您可能会无意中阻止您实际需要的替代解决方案。因此，应该非常深思熟虑地使用它，而不是作为减少输出的快速补丁。
你的程序有几个问题:
- 在调用
false/0之后写入cut,!/0是无用的，因为cut将永远不会到达。试着交换这两个呼叫的顺序。 - 第一个条款可以简化为
oddp(N) :- N mod 2 =:= 1.，您也可以将此简化应用于其他条款。 - 谓词
not/1最好考虑弃用。改为写evenp(N) :- + oddp(N).。(+)/1是将否定作为失败的标准操作/控制结构。