;; filter function

(defun filter (p l) 
       (cond ((null l)  ())
       	     ((p (car l)) (cons (car l) (filter p (cdr l))))
       	     (t (filter p (cdr l)))
	     )
)

;; indivisibility predicate
(defun indivisible (m) (
  lambda (n) 
  (not (zerop (% n m)))
 )
)

;; the sieve of Eratosthenes

(defun sieve (l)
       (if (null l)	
       	  ()
	  (cons (car l) (sieve (filter (indivisible (car l)) (cdr l))))
	  )
)

;; produce a list of numbers from n to m to feed to the sieve
(defun fromto (n m) 
       (if (> n m) 
       	   () 
	   (cons n (fromto (+ n 1) m))
	   )	 
)

;; compute the primes up to n using these functions

(defun primes (n) 
       (sieve (fromto 2 n))
)

;;-----------------------------------------------
;; tail recursive versions are below
;;
;; these should be able to produce more primes than the
;; above before running out of stack space
;;-----------------------------------------------

(defun filter* (p l)
       (reverse (filter-h p l ()))
)

; helper function for filter

(defun filter-h (p l done)
       (cond ((null l) done)
       	     ((p (car l)) (filter-h p (cdr l) (cons (car l) done)))
	     (t (filter-h p (cdr l) done))
	     )
)


; tail-recursive fromto

(defun fromto* (n m l)
  (if (> n m) 
      l 
      (fromto* n (- m 1) (cons m l))
      )
)

; tail-recursive sieve with helper function

(defun sieve-h (l sieved) 
       (if (null l) 
       	   sieved
	   (sieve-h (filter* (indivisible (car l)) (cdr l)) (cons (car l)
       sieved))
  )      
)

(defun sieve* (l) 
       (reverse (sieve-h l ()))
)

; tail-recursive function to compute primes up to n

(defun primes* (n) 
       (sieve* (fromto* 2 n ()))
)