定义 ISPRIME 函数时遇到问题

Question

我是 LISP 的新手，正在解决一些初学者问题。我尝试定义一个 ISPRIME 函数，但它似乎无法正常工作。这是我的代码：

 (defun ISPRIME (n &optional (d (- n 1))) 
      (if (= d 0)
           ( return-from ISPRIME t )) 
      (if (= (mod n d) 0)
           ( return-from ISPRIME nil )) 
      (ISPRIME n (- d 1)))

但是在运行我的代码中，我使用值 5 作为示例：

 (ISPRIME 5)
 Nil

5应该是素数。我怀疑一切都落入了：(if (= (mod n d) 0) 语句，而它不应该是。d 应该继续递减直到达到 0 并返回 true，但它没有。我似乎看不出我的逻辑错误在哪里。

非常感谢任何帮助！

Answer 1

你的代码中有一个错误：函数应该停在 1，而不是 0，因为任何数字都可以被 1 整除。只需这样更改函数即可：

(defun ISPRIME (n &optional (d (- n 1))) 
      (if (= d 1)                         ; <- change from 0 to 1
           ( return-from ISPRIME t )) 
      (if (= (mod n d) 0)
           ( return-from ISPRIME nil )) 
      (ISPRIME n (- d 1)))

但是请注意，您的函数不是很有效，因为 return-from returns 来自函数的最后一次调用，而不是来自“递归塔”，因此您的函数可以重写为以这种方式消除它，通过使用更紧凑的“条件”cond，而不是 if，并将 return-from 替换为结果：

(defun isprime (n &optional (d (- n 1)))
  (cond ((= d 1) t)
        ((= (mod n d) 0) nil)
        (t (isprime n (- d 1)))))

这仍然是递归的，但更符合 Common Lisp 的习惯。当然，可以将此函数转换为更高效的迭代版本，并应用更多 efficient algorithm. Note, however, that a smart compiler will transform automatically this function in iteration, due to the fact that the function is tail recursive.

已添加

您还可以添加初始检查参数 n 是否大于 1，例如：

(defun isprime (n &optional (d (- n 1)))
  (cond ((<= n 1) nil)
        ((= d 1) t)
        ((= (mod n d) 0) nil)
        (t (isprime n (- d 1)))))

Answer 2

由于您正在计算布尔值，因此 (if test T NIL) 的实例可以替换为 test 并且更一般地说，结果可能可以表示为单个布尔表达式。我倾向于发现它们更具可读性。以下是对已接受答案的一点修改作为示例：

(defun is-prime (n &optional (d (1- n)))
  (or (= d 1)
      (and (plusp d)
           (plusp (mod n d))
           (is-prime n (1- d)))))

为了完整起见，根据 Will Ness 的回答，这里是一个 LOOP 版本：

(defun is-prime (n)
  (loop
     for d = 2 then (+ d add)
     for add = 1 then 2
     thereis (> (* d d) n)
     until (= (mod n d) 0)))

和等效的 DO 版本：

(defun is-prime (n)
  (do ((d 2 (+ d add))
       (add 1 2))
      ((> (* d d) n) t)
    (when (zerop (mod n d))
      (return nil))))

Answer 3

你不应该使用（尾）递归，因为 Common Lisp 没有 tail call optimization 保证。使用 do 或 loop，甚至 prog 和 go。

并且在算法上，总是测试你的潜在除数在增加顺序，从2开始，超过(sqrt n)[=43=就停止]:

(defun ISPRIME (n) (prog ((d 2)) ; defines implicit block named NIL LOOP (if (> (* d d) n) ( return-from ISPRIME t )) ; (return T) also works (if (= (mod n d) 0) ( return-from ISPRIME nil )) ; or just (return) (if (= d 2) (incf d 1) (incf d 2)) (go LOOP)))

(return)等同于(return nil)，(return val)等同于(return-from NIL val)。由于 prog 定义了一个名为 NIL 的隐式块，更短、更通用，因此可以在那里使用对 return 的调用。

一个有趣的方法是使用一个可扩展的素数列表，通过使用这个isprime函数过滤递增的数字来创建，用作除数提供另一个 isprime-p 函数，它只会通过这些素数而不是所有可能性来测试其参数，从而实现另一个算法性能增益。素数列表应根据需要进行扩展。素数只会上升到被测试数字的平方根，而素数本身只需要被数字测试到最高素数的平方根（因此，被测试数字的四次方）。

定义 ISPRIME 函数时遇到问题

Trouble with defining an ISPRIME function

lisp

common-lisp

primality-test