Sundaram's sieve in Common Lisp
(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 (&gt; start half)
            (return (remove 0 numbers))))))


Runs fast.

CL-USER 36 &gt; (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)