Lisp - "when" condition executing no matter what?

Question

I'm defining a function to test if a number is prime and I have an algorithm which works (in Python) and I have ported most of it to Lisp. The problem however is that my primality test keeps passing even when it shouldn't. For example, isPrime(13) still reaches the return NIL even though it should fail the when condition.

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

Question: Why does my function reach the return NIL branch no matter what?

Also, if this is just a bad approach to testing primality, is there a more lisp-like way of doing this (not worried about performance, just algorithmic correctness and readability.)

Answer 1

First of all your code has a fairly obvious bug: once you've hit the (> n 2) case of the cond then either it's going to explicitly return nil or it will get to the end of the loop and ... implicitly return nil. The final case of the cond will never be reached.

Here is a version of it which

• is formatted using standard Lisp conventions not ones imported from C or somewhere;
• uses a conventional Lisp name for the function;
• uses better operations (compare numbers with = not equal, for instance);
• uses better bounds on the loop and a better step (no need to check even numbers, you've just done that);
• fixes the bug.

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

However a more natural way to express this in Lisp might well be to say what you would say in English:

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.

Which we would write like this

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

Finally you might want to check that the argument has a reasonable type: primality testing makes sense for natural numbers, so:

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