Generating and using a list of prime numbers

Question

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

Answer 1

for one thing, (eq nil p) is usually written (not p).

the variable p participating only in that do should be declared inside it, not outside it in the enclosing let. Everything should be in its proper place. Same with result - make do your last form and use the return clause of do to return the result:

(defun plist (n)
  (let (
        (arr (make-array (+ n 1) :element-type 'boolean :initial-element t))
       )
    (setf (aref arr 0) nil)
    (setf (aref arr 1) nil)

    (do ( (p 3) 
          (result (list 2))) 
        ( (not p)  (nreverse result))

      (push p result)   ; and what if n==2 ??
      ....
      )))

Don't mix arefs and svrefs, be consistent. Again, the test (when (eq t (svref arr i)) ...) would normally be written just as (when (svref arr i) ...).

Your do loop is a little buggy: it adds 3 unconditionally, even if n < 3. Reorganize. Or, and since you don't inspect them, no need to mark 0 and 1 as non-primes, just like we don't bother with the evens. Which means we get to declare the array inside the do's scope too:

(defun plist (n)
  (do ((arr (make-array (+ n 1) :element-type 'boolean :initial-element t))
       (result (list 2))
       (p      3        (+ p 2))) 
      ((> p n)
       (nreverse result))       ; return form
    (when (aref arr p)
        (push p result)
        (if (<= p (/ n p))   
          (loop for i from (* p p) to n by (* 2 p)
            do (setf (aref arr i) nil))))))

An algorithmic improvement, though you didn't want one: start eliminating multiples of p from (* p p), not from (+ p p), and increment by steps of (* 2 p) among odds only, for twice the speed.

Now that the code is short and compact, we see one more possibility for improvement: if we hit the termination condition, no need to recheck it. Finally, add the documentation string there too:

(defun plist (n)
  "return the list of primes not greater than n. 
   build it by means of the sieve of Eratosthenes."
  (do ((arr (make-array (+ n 1) :element-type 'boolean :initial-element t))
       (result (list 2))
       (p      3        (+ p 2)))   ; a candidate possible prime
      ((> p (/ n p))
       (nconc (nreverse result)
              (loop for i from p to n by 2 if (aref arr i) collect i)))
    (when (aref arr p)              ; not marked as composite: p is prime
        (push p result)  
        (loop for i from (* p p) to n by (* 2 p)  ; mark the multiples
            do (setf (aref arr i) nil)))))

I don't find micro-commenting adding much clarity (even the opposite), but YMMV. Variable names like arr and result are self-documenting.