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!
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.