[Shootout-list] nsieve in Lisp

[Dima Dorfman]

--jRHKVT23PllUwdXP
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

Attached is a Lisp implementation of nsieve. Tested on CMUCL.

NB: Specifying the array element-type as (integer 0 1) causes CMUCL to
create a bit array. We're supposed to have a separate benchmark for
that, but I don't think it would be fair to go out of our way to break
this optimization. This is a good test of the compiler.

--jRHKVT23PllUwdXP
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="nsieve.lisp"

;;; nsieve benchmark for The Computer Language Shootout
;;; Written by Dima Dorfman, 2005

(defun nsieve (m)
  (declare (type integer m))
  (let ((a (make-array (list m) :initial-element 1
		       :element-type '(integer 0 1))))
    (flet ((clear (i)
	     (loop for j from (+ i i) to (1- m) by i
		   do (setf (aref a j) 0))))
      (loop for i from 2 to (1- m)
	    when (= 1 (aref a i)) do (clear i)
	    count (= 1 (aref a i))))))

(defun test (n)
  (let ((m (* 10000 (expt 2 n))))
    (format t "Primes up to~T~d~T~d~%" m (nsieve m))))

(defun main ()
  (let* ((args #+sbcl sb-ext:*posix-argv*
	       #+cmu extensions:*command-line-strings*
	       #+gcl si::*command-args*)
	 (n (parse-integer (car (last args)))))
    (when (>= n 0) (test n))
    (when (>= n 1) (test (- n 1)))
    (when (>= n 2) (test (- n 2)))))

--jRHKVT23PllUwdXP--