Lisp - 素数

Question

我正在努力学习口齿不清,我对素数有些困难.我需要一个功能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") 

首先,不要print你的结果,只需归还它们.其次,它没有%功能rem.

真正的错误是你如何进行递归调用.你有一个额外的括号:

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

在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)))))

但它不是最有效的方式,也不是最安全的方式.计算起来要好得多,而不是一件事,因为任何数字都可能比较大的数字更有可能.然后,它让我们优化停止的地方.