I think that an iterative approach is better suited to this particular problem. I wrote the following optimized code to generate all primes < up-bound:
;; up-bound is non-inclusive
(define (run-sieve up-bound)
(define bstring (make-bytes up-bound 1))
;; mark even numbers after 2 so we can skip all even numbers in the for loop below
(for ([i (in-range 4 up-bound 2)])
(unsafe-bytes-set! bstring i 0))
(for ([i (in-range 3 (sqrt up-bound) 2)])
(when (unsafe-fx= (unsafe-bytes-ref bstring i)
1)
(for ([multiple (in-range (* i i) up-bound (* i 2))])
(unsafe-bytes-set! bstring multiple 0))))
bstring)
;; get a list of prime numbers from the byte string generated by run-sieve
(define (primes bstring)
;; skip index 0 and even indexes since we know even numbers are not prime
(for/list ([i (in-range 1 (bytes-length bstring) 2)]
[val (in-bytes bstring 1 #f 2)]
#:when (equal? val 1))
i))
I wouldn't recommend using unsafe operations like this in most code, but this code is fairly performant:
(time (length (primes (run-sieve 100000))))
cpu time: 1 real time: 1 gc time: 0
9592
This is calculating the first 9592 primes in about 1ms, and that includes the O(n) length operation. Using a byte string for the representation saves a lot of memory allocation(and time).