更新时间:2023-02-11 16:22:47
参见 http://www.swi-prolog.org/pldoc/man?function=mod/2:
+IntExpr1 mod +IntExpr2
Modulo,定义为 Result = IntExpr1 - (IntExpr1 div IntExpr2) × IntExpr2,其中 div 为地板除法.
+IntExpr1 mod +IntExpr2
Modulo, defined as Result = IntExpr1 - (IntExpr1 div IntExpr2) × IntExpr2, where div is floored division.
所以R
应该是0
.mod
只有一个结果.
So R
should be 0
. mod
has only one result.
一个可行的解决方案是:
A working solution would be:
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
的谓词(同名,两个参数).只为起始值获取额外参数的子函数"通常具有相同的名称.因此,您应该使用 primeNumber
而不是 prime_prime
,尽管在 Prolog 中您通常不使用驼峰式大小写.
By the way, primeNumber/1
(a predicate named primeNumber
, with one argument) is a totally separate predicate from primeNumber/2
(same name, two arguments). A "subfunction" that only gets an extra argument for the start value, is usually given the same name. So instead of prime_prime
you should just use primeNumber
, though in Prolog you normally don't use camelCase.
使用 Sergei Lodyagin 在评论中提出的优化:
Using the optimization that Sergei Lodyagin proposed in the comments:
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)
:
And if you use the predefined predicate between(+Low, +High, ?Value)
:
primeNumber(A) :-
L is floor(sqrt(A)),
\+ (between(2, L, X),
0 is A mod X).
为了进一步减少迭代次数,您只需要测试奇数模块:
And to reduce the number of iterations even further, you only need to test for odd modules:
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)).