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!

Masturbate

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.

Lowspirited

This looks slick. Could you comment on the recursion and parameter passing? Does the function call itself while passing subsequently decreasing second parameter each time? – Sphingosine

@Sphingosine "Does the function call itself while passing subsequently decreasing second parameter each time?" yes. Not all the time, just if it needs to do so -- i.e. if d wasn't 1 (when T is returned), and (rem n d) wasn't 0 (when NIL is returned). – Lowspirited

I see. It seems that the function breaks when called with argument 1. It gives division by zero. – Sphingosine

@Sphingosine right. :) that's what I hint at, with "not ... the most safe [way to call this function]". :) – Lowspirited

Got it. So some checking is in order in the beginning? Also, one can optimize by only checking d = isqrt(n) and below. – Sphingosine

@Sphingosine yes indeed; only in the reverse order, from 2 and up, optimizing "where we stop". – Lowspirited

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.

Bassoon

I see what are you doing here but I was trying to make it recursive. How can I make it recursive and keep only one parameter n ? – Masturbate

Possibly, but this isn't a candidate for tail recursion, so there's not a good reason to make it recursive (Lisp is a lot more than just recursive functions...). Let me see what I can knock together... – Bassoon

Answer 3

I have taken Will Ness's answer as an inspiration and modified the function. Here is the code. Is checks whether 1 is passed as a parameter and makes sure to output nil should that be the case.

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

I am still learning Common Lisp, so if there are problems with this, please let me know.

Phiphenomenon

it is much better to count up from 2 to sqrt(n) (inclusive), instead of counting down from (n-1) to 2. also, Common Lisp doesn't like recursion; your intent is a loop so better write it down as a loop. With loop, or do, or prog even. as for your code, you are still not handling cases where (< n 1). – Lowspirited