Lisp - prime number

Question

I am trying to learn lisp and I have some difficulties with prime numbers. I need a function is-prime and if it is prime I have to return t and if it is not I have to return nil.

(prime 41) => t

(prime 35) => nil

So far I've got:

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

but I have 2 parameters there and I have no idea how to use only one. Plus, it's not working at all. Can anyone help me with this? Thanks!

Answer 1

you have few missteps there:

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

First of all, don't print your results, just return them. Second, there's no % function, it's rem.

The real error is how you make the recursive call. You have an extra pair of parentheses there:

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

in Lisp, parentheses signify a function call; but you don't intend to call n with an argument (- d 1), they both are arguments to is-prime. So we just need to remove those extra parentheses,

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

So what does it do? It counts down: d, (- d 1) ... 1. And when (= d 1), it returns t. So, one way to call it is

(defun is-prime (n &optional (d (- n 1))) 
  (or (= d 1)
      (and (/= (rem n d) 0)
           (is-prime  n (- d 1)))))

but it is not the most efficient way, :) nor the most safe one, either.

It is much better to count up, not down, for one thing, because any random number is far more likely to have a smaller factor than a larger one. Then, it lets us optimize where we stop -- and stopping at the sqrt is much much more efficient, and just as correct.

Answer 2

Well, you're halfway there.

Here's my explanation in English:

You have written in lisp a function is-prime (btw, "yes or no" functions like that are usually named whatever-p in lisp) that tells you if n is relatively prime to d.

What you need to do is go through all d's less than n, and if it's not relatively prime to any of them, return nil, but if after that loop you haven't returned nil, then return t. Your friend here is the function "mod", which tells you whether there is a remainder when its first argument is divided by its second.

Something like:

(defun primep (n)
 (cond
  ((= 1    n)          nil)
   (t
   (loop
     :with root     = (isqrt n)
     :with divisors = (loop :for i :from 3 :to root :by 2 :collect i)
     :for d = (pop divisors)
     :if (zerop (mod n d))
     :do (return nil)
     :else :do (setf divisors (delete-if (lambda (x) (zerop (mod x d))) divisors))
     :while divisors
     :finally (return t)))))

Also, don't print nil, just return nil.