lisp - 定义 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 从函数的最后一次调用返回，而不是从“递归塔”返回，因此您的函数可以通过删除来重写以这种方式，通过使用更紧凑的“条件”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 .但是请注意，智能编译器会在迭代中自动转换此函数，因为该函数是 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)))))