non-recursive-sieve.lisp

(defun sieve (n &aux (list (loop for i from 2 to n collect i)))
  (flet ((fact-p (i n)
           (zerop (mod n i))))
    (loop for (head . rest) = list then (remove head rest :test #'fact-p)
          while head collect head)))


; an iterative prime sieve, which is not limited by stack size

(defun sieve (n &aux (list (loop for i from 2 to n collect i)))  ; helper variable LIST of prime candidates

  (flet ((fact-p (i n)                                           ; local function FACT-P
           (zerop (mod n i))))

        (loop for (head . rest) = list                           ; LOOP over the current list of prime candidates
                                                                 ; on first iteration it is LIST
                                                                 ; built-in destructuring of a list in HEAD and REST

                then (remove head rest :test #'fact-p)           ; calling REMOVE with a special test function
                                                                 ; every next iteration this will be used to update
                                                                 ; HEAD and REST
          
              while head                                         ; end if no candidates are left
              collect head)))                                    ; collecting all the primes


; CL-USER > (sieve 100)
; (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)