The sieve of eratosthenes is a method of finding prime numbers. Prime numbers are numbers that have only 2 integer factors and they are number itself and the number one. First you list all of the numbers greater than one. Then you eliminate the first prime (2). After that you eliminate that prime's multiples. Then you repeat it with the next prime number etc... Below is a program that does this process using lazy evaluation.

This code was altered slightly by r2q2, originally coded by fuse on IRC. Another common approach to the sieve algorithm is to use lazy streams. See SICP for an example, and SRFI:40 for a standardized stream library.

 (define mark 
   (lambda (v a s) 
     (if (< a (vector-length v)) 
         (begin 
           (vector-set! v a '#f) 
           (mark v (+ a s) s))))) 
  
 (define primes 
   (lambda (n) 
     (let ((v (make-vector n))) 
       (vector-fill! v '#t) 
       (let loop ((i 0) 
                  (r '())) 
         (cond ((>= i n) r) 
               ((vector-ref v i) 
                (begin 
                  (mark v i (+ i 2)) 
                  (loop (+ i 1) 
                        (cons (+ i 2) r))) 
                (loop (+ i 1) 
                      r)))))))

If you adapt Donald E. Knuths way of doing the Sieve, it can be done very elegantly.

 (define (primes n) 
   (let ((pvector (make-vector (+ 1 n) #t))) ; if slot k then 2k+1 is a prime 
     (let loop ((p 3) ; Maintains invariant p = 2j + 1 
                (q 4) ; Maintains invariant q = 2j + 2jj 
                (j 1) 
                (k '()) 
                (vec pvector)) 
       (letrec ((lp (lambda (p q j k vec) 
                   (loop (+ 2 p) 
                         (+ q (- (* 2 (+ 2 p)) 2)) 
                         (+ 1 j) 
                         k 
                         vec))) 
                (eradicate (lambda (q p vec) 
                             (if (<= q n) 
                                 (begin (vector-set! vec q #f) 
                                        (eradicate (+ q p) p vec)) 
                                 vec)))) 
          (if (<= j n) 
             (if (eq? #t (vector-ref vec j)) 
                 (begin (display p) 
                        (newline) 
                        (lp p q j q (eradicate q p vec))) 
                 (lp p q j k vec)) 
             #t)))))

The trick is to maintain the p and q values which greatly reduces the amount of computation involved when eradicating a new multiple sequence.

sieve-of-eratosthenes

Sieve of Eratosthenes