Transforming the code to use recursion

Questions & Answers
18

Thanks for the fix in the primes function! I was looking at the total number of primes and never noticed.

I wouldn't remove the first for in run-sieve because that is the real sieve. primes was intended as a convenience function to just count the primes. But to be consistent with that I should remove 0 and 1 as primes in the byte string as well. Here's my updated version:

;; up-bound is non-inclusive
(define (run-sieve up-bound)
  (define bstring (make-bytes up-bound 1))

  (unsafe-bytes-set! bstring 0 0)
  (unsafe-bytes-set! bstring 1 0)
  
  ;; 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)
  (cons 2 
        ;; skip index 0 and even indexes since we know even numbers are not prime
        (for/list ([i (in-range 3 (bytes-length bstring) 2)]
                   [val (in-bytes bstring 3 #f 2)]
                   #:when (equal? val 1))
          i)))
1 Like