segmented sieve of eratosthenes

seg_sieve.rkt

(define (s-sieve limit)
  (define sieve-size (add1 (integer-sqrt limit)))
  (define sieve (make-vector sieve-size #t))
  ; sieve of eratosthenes
  (for* ([i (in-range 2 sieve-size)]
	 #:when (vector-ref sieve i)
	 [j (in-range (* i i) sieve-size i)])
    (vector-set! sieve j #f))
  ; collect sieve
  (define primes (for/list ([n (in-range 2 sieve-size)]
			    #:when (vector-ref sieve n))
		   n))
  ; loop over the rest
  (let loop ([lo sieve-size]
	     [primes-rest '()])
    ; clear the vector
    (for ([i (in-range sieve-size)]) (vector-set! sieve i #t))
    ; sieve
    (for* ([p (in-list primes)]
	   [i (in-range (if (= (modulo lo p) 0)
			    0
			    (- p (modulo lo p)))
			sieve-size p)])
      (vector-set! sieve i #f))
    ; collect new primes
    (for([n (in-range lo (if (> (+ lo sieve-size) limit) limit (+ lo sieve-size)))]
			#:when (vector-ref sieve (- n lo)))
      (set! primes-rest (cons n primes-rest)))
    
    ; return the result
    (if (> (+ lo sieve-size) limit)
	(append primes (reverse primes-rest))
	(loop (+ lo sieve-size) primes-rest))))