fast-prime-sieve.scm

(define (prime-sieve count)
  (let ((marked (make-vector count #f)))

    (define (build-list index)
      (if (>= index count)
        '()
        (if (vector-ref marked index)
          (build-list (+ index 1))
          (cons (+ index 1) (build-list (+ index 1))))))

    (define (next-prime index)
      (if (>= index count)
        marked
        (begin
          (if (vector-ref marked index)
            'done
            (mark (+ index 1) (+ index index 1)))
          (next-prime (+ index 1)))))

    (define (mark stride index)
      (if (>= index count)
        'ok
        (begin
          (vector-set! marked index #t)
          (mark stride (+ index stride)))))

    (begin (next-prime 1) (build-list 1))))