conditional-statements - Lisp - 无论如何执行 "when"条件？

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

首先，您的代码有一个相当明显的错误:一旦您遇到 cond 的 (> n 2) 情况，那么它要么显式返回nil 否则它将到达循环的末尾并...隐式返回 nil。永远不会达到 cond 的最终情况。

这是它的一个版本

• 使用标准的 Lisp 约定格式化，而不是从 C 或其他地方导入的约定；
• 为函数使用传统的 Lisp 名称；
• 使用更好的操作(例如，将数字与 = 而不是 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 is prime if it is 2 or if it is greater 2 and if it is odd, and if it has no odd divisors less than or equal to its square root.

我们会这样写

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