Prime Sieve

sieve.rkt

#lang typed/racket

;; Adapted from http://stackoverflow.com/questions/10384875/why-is-clojure-much-faster-than-mit-scheme-for-equivalent-functions

(: sieve : Positive-Index -> (Listof Integer))
(define (sieve n)
  (let ((#{root : Index} (assert (round (inexact->exact (sqrt n))) index?))
        (#{a : (Vectorof Boolean)} (make-vector n #f)))
    (: cross-out : Integer Fixnum Fixnum -> 0)
    (define (cross-out t to dt)
      (cond ((> t to) 0)
            (else
             (vector-set! a t #t)
             (cross-out (+ t dt) to dt))))
    (: iter : Positive-Fixnum (Listof Integer) -> (Listof Integer))
    (define (iter i result)
      (cond ((>= i n) (reverse result))
            (else
             (when (< i root)
               (cross-out (* i i) (- n 1) (+ i i)))
             (iter (+ i 2) (if (vector-ref a i)
                               result
                               (cons i result)))))) 
    (iter 3 (list 2))))

(time (foldl + 0 (sieve 5000000)))