;  (sieve n) returns a list of prime numbers between 2 and n.
;  This is done iteratively. we successively cross off each multiple  of integer
;  from 2 to sqrt(n). Cnt is the multiple being crossed off.
; A crossed off number is represented by nil; all the nilŐs are deleted from final answer.

(defun sieve (n)
   (let ((nums (nlist 2 n))
	 (cnt 2)
	 (ans nil)
	 (end (ceiling (sqrt n))))
       (loop
	    (cond ((> cnt end) (return (filternils 	
							(append ans nums)))))
	    (setq ans (append ans (list (car nums))))
	    (setq nums (crossoff cnt (cdr nums)))
	    (setq cnt (1+ cnt))
       )
   )
)

; (crossoff n nums) iteratively replaces every nth item in nums with nil.

(defun crossoff (n nums)
   (let ((i 1) (ans nil))
      (loop
	 (cond ((null nums) (return ans)))
	 (cond ((zerop (mod i n))
		    (setq ans (append ans '(nil))))
               (t (setq ans (append ans (list (car nums)))))
          )
	  (setq i (1+ i))
	  (setq	nums (cdr nums))
       )
   )
)

; (nlist a b) recursively creates a list of integers from a to b

(defun nlist (a b)
     (cond ((>= a b) (list b))
	   (t  (cons a (nlist (1+ a) b) ) )
     )
)

; (filternils m) recursively removes all nil's from list m


(defun filternils (l)
   (cond ((null l) nil)
	 ((null (car l)) (filternils (cdr l)))
	 (t (cons (car l) (filternils (cdr l))))
   )
)