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.