The `range` function produces a list, which is a big overhead for each time the inner loop executes. There's a big improvement changing the inner loop sequence clause to just [p n]. There's a bit more improvement making that [p (in-range n)], which is recognized statically at expansion time by the `for` loop to produce better code. See:
http://docs.racket-lang.org/guide/for.html#(part._for-performance) Filtering the final list during building is also an improvement: (for/list ([i (range 2 n)] #:when (vector-ref A i)) i) And let's make it more consistent with the comment style, and consistent with the above changes. This appears to speed it up even more, although I didn't investigate where exactly the big win(s) were: #lang racket ;; Input: an integer n > 1 (define (sieve-of-eratosthenes n) ;; Let A be an array of Boolean values, indexed by integers 2 to n, ;; initially all set to true. ;; for i = 2, 3, 4, ..., √n : ;; when A[i] is true: ;; for j = i², i²+i, i²+2i, ..., n: ;; A[j] := false (define A (make-vector n #t)) (for ([i (in-range 2 (sqrt n))] #:when (vector-ref A i)) (for ([j (in-range (sqr i) n i)]) (vector-set! A j #f))) ;; Now all i such that A[i] is true are prime. (for/list ([i (in-range 2 n)] #:when (vector-ref A i)) i)) (time (apply + (sieve-of-eratosthenes 2000000))) ____________________ Racket Users list: http://lists.racket-lang.org/users
