Prolog 中的素数测试谓词 isPrime/1

Question

我试图理解练习的解决方案以准备我的逻辑编程考试，但不知何故我无法理解下面代码的逻辑。

题中的解释：

n is a prime number n > 1 and 1 < m < n n/m has a non-zero remainder.

代码如下：

isPrime(X) :- help(X,X).

help(X,Y) :-
   Y > 2,
   LOW is Y-1,
   Z is X mod LOW,
   Z > 0,
   help(X,LOW).
help(X,2).

谁能帮我解释一下代码。

Answer 1

此代码试图通过执行以下操作来确定 X 是否为质数：

let Y = X initially
1. Check to see if the number (Y) is greater than 2.
2. Assign a new variable (LOW) one-less than the starting number (Y-1)
3. If X mod LOW is greater than zero, then recurse with LOW as the new Y

重复此操作直到 X mod LOW 大于零并且您的 mod 为 1 (Y=2)，然后如果我正确地阅读了此内容（并记住了公式），您应该以 X 为素数。

If at some point X mod LOW equals zero, then X is a non-prime.
Example:  X=6 (non-prime)
Y=6, LOW=5, Z = 6 mod 5 = 1 --> help(6,5)
Y=5, LOW=4, Z = 6 mod 4 = 2 --> help(6,4)
Y=4, LOW=3  Z = 6 mod 3 = 0  --> non prime because it's divisible by 3 in this case

Example: X=5 (prime)
Y=5, LOW=4, Z= 5 mod 4 = 1  --> help(5,4)
Y=4, LOW=3, Z= 5 mod 3 = 2  --> help(5,3)
Y=3, LOW=2  Z= 5 mod 2 = 3  --> help(5,2)
Y=2, --> once you get to this point, X is prime, because LOW=1, 
and any number mod 1 is greater than zero, and you can't "X mod 0".

有道理吗？它有效地迭代小于 X 的数字以查看它是否平均分配 (mod = 0).

Answer 2

好的。质数的定义：

An integer n is prime if the following holds true:

N is greater than 1, and

N is divisible only by itself and 1.

由于每个整数 (A) 都可以被自身整除，并且 (B) 可以被 1 整除，所以没有必要检查这些条件是否成立。必须检查的真正约束是：

For a number n to be prime, the following constraints must be satisfied:

n must be greater than 1, and

No m must exist in the domain 1 > m < n such that n is divisible by m

您的 help/2 谓词强制执行第二个约束，方法是用测试值作为第二个参数的种子，然后递减它，寻找除以 [=22] 的 m =]n.

一种更简单的方法可能是以声明方式编写测试，然后让 Prolog 为您解决：

is_prime(2).         % 2 is prime by definition.
is_prime(N) :-       % otherwise, N is prime if,
  N > 2 ,            % - N is greater than 2, and
  0 =\= N mod 2      % - and N is odd (no real need to check even numbers, eh?
  not_divisible(3,N) % - and N is not divisible any other odd number in the range 3 -- (N-1) 
  .

not_divisible(N,N) .  % if we've counted up to N, we're good.
not_divisible(M,N) :- % otherwise...
  M < N ,             % - if M is less than N, and
  0 =:= N mod M       % - and N is not divisible by M, then
  M1 is M-1 ,         % - decrement M, and
  not_divisible(M1,N) % - recurse down on the newly decremented M
  .                   %

Prolog 中的素数测试谓词 isPrime/1

Primality test predicate isPrime/1 in Prolog

primes

prolog