; yet another sift program

(defun sieve3 (n)
   (filternils (sift 2 (ceiling (sqrt n)) (nlist 2 n)))
)

; (see sieve2.lsp)

(defun sift (cnt end nums)
  (cond ((> cnt end) nums)
	(t (cons (car nums) (sift (1+ cnt) end 
						(sift_thru cnt (cdr nums)))
	   )
        )
  )
)

; sift_thru uses a purely symbolic means to strike multiples off the list.
; To strike off ith multiples, mask creates: (for eg. i=3)
;	t t nil t t nil t t nil ....
;  Then AND this with nums, and the nil entries strike off the numbers
; This isnt necessarily efficient; but it is interesting computationally speaking.
; Note that the mask created actually exceeds the length of nums; however, mapcar will
; quit at the end of nums, so no problems occur.

(defun sift_thru (i nums)
   (mapcar #'(lambda (x y) (and x y)) (mask i (length nums)) nums)
)


(defun mask (i n)
   (repeat (ceiling (/ n i)) (append (repeat (1- i) '(t)) '(nil)))
)

(defun repeat (i s)
   (cond ((zerop i) nil)
	 (t (append s (repeat (1- i) s)))
   )
)


; (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))))
   )
)