Sundaram's sieve in Common Lisp

Question

I have this Sundaram's sieve to generate prime numbers up to limit in Common Lisp.

(defun sundaram-sieve (limit)
 (let ((numbers (range 3 (+ limit 1) 2))
 (half (/ limit 2))
 (start 4))
 (dolist (step (range 3 (+ limit 1) 2))
 (dolist (i (range start half step))
 (setf (nth (- i 1) numbers) 0))
 (setq start (+ start (* 2 (+ step 1))))
 (if (> start half)
 (return (cons 2 (remove-if #'zerop numbers)))))))

Here range is defined as:

(defun range (min max step)
 (loop for n from min below max by step
 collect n))

How can i make the code above more functional and idiomatic? The use of setq and setf bothers me, not to mention that it takes 10 seconds to calculate with limit equal 100000, when the equivalent code in Python runs almost instantly.

Answer 1

 (let ((numbers (range 3 (+ limit 1) 2))

Above defines a list of numbers. Later you set various numbers to zero. That's not good for a list structure. Use a vector, an one-dimensional array.

(dolist (step (range 3 (+ limit 1) 2))

Creating the list and then iterating over it makes no sense. Use a LOOP statement directly.

 (dolist (i (range start half step))

Creating the list and then iterating over it makes no sense. Use a LOOP statement directly.

Example:

(defun sundaram-sieve (limit)
 (let ((numbers (coerce (cons 2 (range 3 (+ limit 1) 2)) 'vector))
 (half (/ limit 2))
 (start 4))
 (loop for step from 3 upto limit by 2 do
 (loop for i from start below half by step do
 (setf (aref numbers i) 0))
 (incf start (* 2 (1+ step)))
 (when (> start half)
 (return (remove 0 numbers))))))

Runs fast.

CL-USER 36 > (time (sundaram-sieve 100000))
Timing the evaluation of (SUNDARAM-SIEVE 100000)
User time = 0.007
System time = 0.000
Elapsed time = 0.004
Allocation = 1646136 bytes
0 Page faults
#(2 3 5 7 11 13 17 ... 99971 99989 99991)

Answer 2

You don't need to iterate up to limit but only up to (isqrt limit).

• bpecsek: The outer loop iterates upto limit by 2. That should be changed to upto (isqrt limit) by 2