8

我正在尝试学习 lisp，但我在质数方面遇到了一些困难。我需要一个函数is-prime，如果它是素数，我必须返回t，如果不是，我必须返回nil。

(prime 41) => t

(prime 35) => nil

到目前为止，我有：

(defun is-prime (n d) 
  (if (= d 1) 
      (print "t") 
      (if (= (% n d) 0) 
          (print "nil") 
          (is-prime (n (- d 1) )))))

但我在那里有 2 个参数，我不知道如何只使用一个。另外，它根本不起作用。谁能帮我这个？谢谢！

4

3 回答 3

7

你有几个失误：

(defun is-prime (n d) 
  (if (= d 1) 
      (print "t") 
      (if (= (% n d) 0) 
          (print "nil")

首先，不要print你的结果，只是返回它们。其次，没有%功能，就是rem.

真正的错误是你如何进行递归调用。你有一对额外的括号：

          (is-prime (n (- d 1) )))))
          ;         ^          ^
          ;        this      and this

在 Lisp 中，括号表示函数调用；但你不打算n用参数调用(- d 1)，它们都是is-prime. 所以我们只需要删除那些多余的括号，

          (is-prime  n (- d 1)  ))))

那么它有什么作用呢？它倒计时：d, (- d 1)... 1. 而什么时候(= d 1)，它又回来了t。所以，一种叫法是

(defun is-prime (n &optional (d (- n 1))) 
  (or (= d 1)
      (and (/= (rem n d) 0)
           (is-prime  n (- d 1)))))

但这不是最有效的方法，:) 也不是最安全的方法。

一方面，向上计数而不是向下计数要好得多，因为任何随机数都比较大的随机数更有可能具有较小的因子。然后，它可以让我们优化我们停止的位置 - 并且在停止位置sqrt更有效，并且同样正确。

于 2013-12-15T23:12:31.720 回答
3

好吧，你已经成功了一半。

这是我的英文解释：

您已经在 lisp 中编写了一个函数 is-prime（顺便说一句，类似的“是或否”函数在 lisp 中通常被命名为whatever-p），它告诉您 n 是否相对于 d 是质数。

您需要做的是遍历所有小于 n 的 d，如果它与其中任何一个都不是相对质数，则返回nil，但如果在该循环之后您还没有返回nil，则返回t。你的朋友是函数“mod”，它告诉你当它的第一个参数除以它的第二个参数时是否有余数。

就像是：

(defun primep (n)
 (cond
  ((= 1    n)          nil)
   (t
   (loop
     :with root     = (isqrt n)
     :with divisors = (loop :for i :from 3 :to root :by 2 :collect i)
     :for d = (pop divisors)
     :if (zerop (mod n d))
     :do (return nil)
     :else :do (setf divisors (delete-if (lambda (x) (zerop (mod x d))) divisors))
     :while divisors
     :finally (return t)))))

另外，不要打印 nil，只返回 nil。

于 2013-12-15T22:41:53.367 回答
1

我以 Will Ness 的回答为灵感并修改了函数。这是代码。Is 检查 1 是否作为参数传递，并确保nil在这种情况下输出。

(defun is-prime (n &optional (d (- n 1))) 
  (if (/= n 1) (or (= d 1)
      (and (/= (rem n d) 0)
           (is-prime  n (- d 1)))) ()))

我还在学习 Common Lisp，所以如果有问题，请告诉我。

于 2016-11-03T20:46:10.337 回答