ICPC2011ProblemA

チェビシェフの定理

(defun sieve-of-erathostenes (num)
  (let ((sieve (make-array num :initial-element 1)))
    (setf (aref sieve 0) 0)
    (loop for i from 1 upto (sqrt num)
       when (= 1 (aref sieve i))
       do
	 (loop
	    for j from (1+ i)
	    until (> (* (1+ i) j) num)
	    do
	      (setf (aref sieve (1- (* (1+ i) j))) 0)))
    sieve))

(defun count-primes (num)
  (let ((sieve (sieve-of-erathostenes (* num 2))))
    (loop for n from (1- num) upto (1- (* num 2))
	 count (= 1 (aref sieve n)))))

(defun main ()
  (loop
     for n = (read)
     until (zerop n)
     do
       (format t "~A~%" (count-primes n))))

配列を利用している所がミソですかね。リストにすると、重くてメモリ量もすごい事になります。