Here is some code I've created to generate and use a list of prime numbers. This is some of the first Common Lisp code I've written, and I'd be grateful for any comments regarding style and its use or misuse of common idioms. I'm not really interested in improving the algorithm, but in making my implementation readable and efficient.
;;; Estimate the number of primes below a number n (defun primes-pi (n) (ceiling (/ n (- (log n) 1)))) ;;; (A high) estimate of the number below which there are n primes, this is the ;;; reverse of primes-pi (defun primes-n (n) (* n (ceiling (+ (log n) 1)))) ;;; Code to generate prime numbers (defun plist (n) (let (;; An array of booleams flags for the sieve (arr (make-array (+ n 1) :element-type 'boolean :initial-element t)) ;; The first prime the loop below will handle (p 3) ;; results is used to build the list of primes (result nil)) ;; 0 isn't prime (setf (aref arr 0) nil) ;; 1 isn't prime (setf (aref arr 1) nil) ;; 2 is primes (push 2 result) ;; Now the special cases are out of the way start sieving for new primes ;; when p is nil the loop has reached the end of the arr array (do () ((eq nil p)) ;; add p to the list of primes (push p result) ;; Remove all multiples of p from the array (loop for i from (+ p p) to n by p do (setf (aref arr i) nil)) ;; search forward in the array to the next non nil entry, this will be ;; the next prime. (setf p (loop for i from (+ 2 p) to n by 2 when (eq t (svref arr i)) return i))) ;; reverse the list to get the primes in ascending order ;; not really needed if only using the list in build-is-prime? (nreverse result))) ;;; This function creates and returns a closure that allows testing ;;; for primeality of at least the first n prime number (defun build-is-prime (n) (let ((prime-table (make-hash-table :size n))) ;; Populate the hash table (loop for i in (plist (primes-n n)) do (setf (gethash i prime-table) t)) ;; Lambda to test for presence of p in the hash table (lambda (p) (gethash p prime-table) )))