定义ISPRIME函数的麻烦

我对LISP非常陌生，并且正在解决一些初学者问题。我试着定义一个ISPRIME函数，但它似乎没有正常工作。这里是我的代码：定义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，但它不。看到这里我的逻辑错误是发生

任何及所有的帮助感激

来源

2016-09-16 John Bucher

'（mod 5 1）'。另外，你应该使用['COND']（http://www.lispworks.com/documentation/HyperSpec/Body/m_cond.htm）而不是'IF' +'RETURN-FROM's。 – jkiiski

。在你的代码中的错误：！功能应该停留在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回报

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

：ction，而不是从“递归塔”，所以你的功能，可通过消除它以这种方式，通过使用更紧凑的“条件” cond，而不是 if，并用结果替代 return-from改写

这仍然是递归的，但对于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)))))

来源

2016-09-16 05:37:11 Renzo

@coredump，谢谢，我修改了答案。 – Renzo

既然你是计算一个布尔值，的(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)))))

为了完整，并根据从威尔尼斯的答案，这里是一个循环的版本：

(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-16 07:24:11 coredump

['loop loop finish]]（http://clhs.lisp.se/Body/m_loop_f.htm）（这是由'until'触发的，AFAICS）没有明确说明当没有值被累加时返回的内容，并没有定义循环结语子句。显然它会返回NIL，但是，CLHS中有没有明确说明的地方，你知道吗？ –

@WillNess最相关的规范部分将是“*除非其他子句贡献返回值，否则在[6.1.4终止测试子句]（http://www.lispworks.com/）中返回的缺省值为nil。*”文档/ lw51/CLHS/Body/06_ad.htm），用于'thereis'子句。这种特殊的组合看起来很好，但我肯定希望得到更正式的保证。 – coredump

我想...感谢报价/链接。或者最后一个子句'finally（return NIL）'可以被添加，只是为了明确。与'（return-from is-prime）'相同，可以写成'（return nil）'（使用'return'也有助于如果想要重命名函数... :)）。因人而异。 :) –

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

而且算法，总是测试你在增加顺序，从开始电位为约数，并停止当你超过(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-from NIL val)相同。由于prog定义了一个名为NIL的隐式块，因此可以使用更短且更一般的调用return来代替。

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

来源

2016-09-16 23:28:12

定义ISPRIME函数的麻烦

回答

相关问题