Lisp - 无论如何执行“何时”条件？

Question

我正在定义一个函数来测试一个数字是否为素数，并且我有一个有效的算法（在 Python 中）并且我已经将它的大部分移植到 Lisp。然而，问题是我的素性测试即使在不应该通过的情况下也一直通过。例如，isPrime(13)仍然达到return NIL即使它应该失败的when条件。

(defun isPrime(n)
    (cond 
        ((< n 2); numbers less than 2 aren't prime
            NIL
        )
        ((equal n 2); 2 is the only even prime
            T
        )
        ((equal (rem n 2) 0); Even numbers are never prime (besides 2)
            NIL
        )
        ((> n 2)
            (loop for i from 2 to n do(
                    when(equal (rem n i) 0);If n is evenly divisible by i, we have found a factor other than 1 and n
                        (return NIL)                   
                )
            ) 
        )
        (t T); If we get through all that with no issue, the number is prime
    )
)

问题：为什么我的函数return NIL无论如何都会到达分支？

此外，如果这只是测试素性的一种糟糕方法，是否有更类似于 lisp 的方法（不担心性能，只担心算法的正确性和可读性。）

Answer 1

首先，你的代码有一个相当明显的错误：一旦你遇到(> n 2)了condthen的情况，要么它会显式返回，nil要么它会到达循环的末尾并......隐式返回nil。cond永远不会到达最后的情况。

这是它的一个版本

• 使用标准 Lisp 约定格式化，而不是从 C 或其他地方导入的约定；
• 为函数使用传统的 Lisp 名称；
• 使用更好的操作（例如将数字与=not进行比较equal）；
• 在循环中使用更好的边界和更好的步骤（无需检查偶数，您已经完成了）；
• 修复了错误。

(defun primep (n)
  (cond
   ((< n 2)
    ;; numbers less than 2 are not prime
    nil)
   ((= n 2)
    ;; 2 is prime
    t)
   ((evenp n)
    ;; even numbers are not prime
    nil)
   (t
    ;; Otherwise it is a prime if no odd integer less than or equal to
    ;; its root divides it.
    (loop for i from 3 to (isqrt n) by 2
          never (zerop (rem n i))))))

然而，在 Lisp 中表达这一点的更自然的方式很可能是用英语说出你会说的话：

如果 n 为 2或大于 2且为奇数，并且没有小于或等于其平方根的奇数除数，则n 为素数。

我们会这样写

(defun primep (n)
  (or (= n 2)                           ;2 is prime ...
      (and                              ;... otherwise ...
       (> n 2)                          ;... primes must be > 2 ...
       (oddp n)                         ;... odd ...
       ;; ... and have no odd divisorts <= their roots
       (loop for i from 3 to (isqrt n) by 2
             never (zerop (rem n i))))))

最后，您可能想要检查参数是否具有合理的类型：素性测试对自然数有意义，因此：

(defun primep (n)
  (check-type n (integer 0) "a natural number")
  (or (= n 2)                           ;2 is prime ...
      (and                              ;... otherwise ...
       (> n 2)                          ;... primes must be >= 2 ...
       (oddp n)                         ;... odd ...
       ;; ... and have no odd divisorts <= their roots
       (loop for i from 3 to (isqrt n) by 2
             never (zerop (rem n i))))))