Lisp - prime number
Solution 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.
Solution 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.
Solution 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.
Related videos on Youtube
mad scientist
Updated on June 25, 2022Comments
-
mad scientist almost 2 years
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 returnt
and if it is not I have to returnnil
.(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!
-
mad scientist over 10 yearsI 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 ?
-
Bandrami over 10 yearsPossibly, 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...
-
ArtforLife over 7 yearsThis looks slick. Could you comment on the recursion and parameter passing? Does the function call itself while passing subsequently decreasing second parameter each time?
-
Will Ness over 7 years@ArtforLife "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't1
(whenT
is returned), and(rem n d)
wasn't0
(whenNIL
is returned). -
ArtforLife over 7 yearsI see. It seems that the function breaks when called with argument 1. It gives division by zero.
-
Will Ness over 7 years@ArtforLife right. :) that's what I hint at, with "not ... the most safe [way to call this function]". :)
-
ArtforLife over 7 yearsGot it. So some checking is in order in the beginning? Also, one can optimize by only checking
d = isqrt(n)
and below. -
Will Ness over 7 years@ArtforLife yes indeed; only in the reverse order, from 2 and up, optimizing "where we stop".
-
Will Ness over 7 yearsit 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
, ordo
, orprog
even. as for your code, you are still not handling cases where(< n 1)
.