CODEWITHSUNDEEP
lispcommon-lispprimesclisp
sef sf
sef sf

Reputation: 119

Loop goes over numbers and checks for primes - primes are not detected

So I'm, trying to learn lisp, and I figured an easy program to help me learn it is just a program that checks for primes. It worked at first:

(dotimes (i 100)
    (let ((devisors 0)) 
        (if (> i 2) 
            (progn
            (dotimes (j (+ (/ i 2) 1))
            (if (> j 1) 
                (if (= (rem i j) 0) (setq devisors 1) )
            ))
            (if (= devisors 0) (print i))
            )
        )
    )
)

I then tried to abstract the prime checking into a function, and wrote this code:

(defun isprime (num) 
    (defvar devisors 0)
    (dotimes (j (+ (/ num 2) 1))
    (if (> j 1) 
        (if (= (rem num j) 0) (setq devisors 1) )
    ))
    (if (= devisors 0) num 0)
)

(dotimes (i 100) 
    (if (/= (isprime i) 0) (print i))
)

But this one doesn't work. It prints 123 and finishes. The thing is, I tried to just print (print (isprime 5)) and IT WORKS but it doesn't when in the loop.

Why is this? Also keep in mind I'm new to lisp... (I'm using clisp if it helps)

Upvotes: 0

Views: 118

Answers (2)

Chris
Chris

Reputation: 36611

Your first step should be to break the question down. You need to know if anything in a range of numbers meets a criteria represented as a predicate function. This is readily accomplished with simple recursion, and is naturally tail-recursive.

(defun any-in-range (s e predicate)
  (cond ((> s e) nil)
        ((funcall predicate s) t)
        (t (any-in-range (+ 1 s) e predicate))))

Now checking if something is prime is just looking to see if any number in a range is a divisor of an input number. The range will be 2 to the square root of the input number.

(defun is-prime (n) 
  (not (any-in-range 2 (floor (sqrt n))
                    (lambda (x) (= 0 (rem n x))))))  

* (is-prime 17)
T
* (is-prime 16)
NIL

Now you can write:

(dotimes (i 100) 
  (when (is-prime i)
    (print i)))

Upvotes: 5

Martin Půda
Martin Půda

Reputation: 7578

Important note: this code shouldn't work. Documentation for dotimes says:

dotimes iterates over a series of integers.

dotimes evaluates count-form, which should produce an integer.

Imagine that i is 3. Then the value of j is 5/2, and that isn't an integer.

But for some reason, this code works in CLISP. Your error is caused by defvar- look again into documentation:

defparameter unconditionally assigns the initial-value to the dynamic variable named name.

defvar, by contrast, assigns initial-value (if supplied) to the dynamic variable named name only if name is not already bound.

When you call isprime with a new number, devisors is already set to 1, so it won't reset to 0.

Quick fix- replace (defvar devisors 0) with (let ((devisors 0)) ... inside isprime.

I also made some other changes (zerop, 1+ and floor, when instead of if with only one branch, and also directly returning t (true) or nil (false) instead of some 0 or 1):

(defun isprime (num)
  (if (or (zerop num)
          (= num 1)) 
      nil
    (let ((devisors t))
      (dotimes (j (1+ (floor (sqrt num))))
        (when (> j 1) 
          (when (zerop (rem num j)) 
            (setq devisors nil))))
      devisors)))

(dotimes (i 100) 
  (when (isprime i)
    (print i)))

Upvotes: 4

Related Questions