s c h e m a t i c s : c o o k b o o k

;; return a a byte vector representation of the primes between 3 and
;; `size'
(define (make-base-block size)
  (let ((block (make-byte-vector size 1))
        (limit (inexact->exact (truncate (/ (sqrt (* size 2)) 2)))))
    (do ((i 0 (+ 1 i)))
        ((>= i limit) block)
      (if (= (byte-vector-ref block i) 1)
          (let ((prime (+ (* i 2) 3)))
            (do ((k (+ i prime) (+ k prime)))
                ((>= k size) #t)
              (byte-vector-set! block k 0)))))))

;; Given a block of primes in base-block (which must cover the primes
;; up to `(sqrt (+ base (byte-vector-length block)))', set all
;; locations in `block' to 1 that are prime and all others to 0.
(define (sieve-block! base-block base block)
  (byte-vector-fill! block 1)
  (let* ((size (byte-vector-length block))
         (limit (quotient (truncate (sqrt (+ base (* size 2)))) 2)))
    (do ((i 0 (+ i 1)))
        ((>= i limit) block)
      (if (= (byte-vector-ref base-block i) 1)
          (let* ((prime (+ (* i 2) 3))
                 (multiple (let loop ((multiple (* (quotient base prime) prime)))
                             (if (or (< multiple base)
                                     (= (remainder multiple 2) 0))
                                 (loop (+ multiple prime))
                                 multiple))))
            (do ((k (quotient (- multiple base) 2) (+ k prime)))
                ((>= k size) #t)
              (byte-vector-set! block k 0)))))))