2

我对 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 nd) 0) 语句不应该出现的情况。d 应该继续递减直到达到 0 并返回 true，但事实并非如此。我似乎无法看看我的逻辑错误发生在哪里。

非常感谢任何和所有帮助！

4

3 回答 3

4

您的代码中有一个错误：函数应该停在 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 来说更惯用。当然，可以将这个函数转换为更有效的迭代版本，并应用更有效的算法。但是请注意，智能编译器将在迭代中自动转换此函数，因为该函数是尾递归的。

添加

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)))))
于 2016-09-16T05:37:11.330 回答
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 的回答，这里是一个循环版本：

(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))))
于 2016-09-16T07:24:11.053 回答
2

你不应该使用（尾）递归，因为 Common Lisp 没有尾调用优化保证。使用doorloop代替，甚至prog使用go.

并且在算法上，始终以递增的顺序测试您的潜在除数，从2开始，并在超过 时停止(sqrt n)：

(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函数中的除数供应，它只会通过这些素数而不是所有的可能性来测试它的参数，因此实现另一个算法性能增益。应根据需要扩展素数列表。质数只会上升到被测试数字的平方根，而质数本身只需要被数字测试到最高质数的平方根（因此，被测试数字的第四根）。

于 2016-09-16T23:28:12.500 回答