Lisp - 素数

Question

我正在尝试学习 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 个参数，我不知道如何只使用一个。另外，它根本不起作用。谁能帮我这个？谢谢!

Answer 1

你有几个失误:

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

首先，不要打印您的结果，只返回它们。其次，没有% 函数，它是rem。

真正的错误在于你如何进行递归调用。那里有一对额外的括号:

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

在 Lisp 中，括号表示函数调用；但是您不打算使用参数 (- d 1) 调用 n，它们都是 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 停止会更有效率，而且同样正确。多。 p>