sieve.clj

gistfile1.clj

(set! *unchecked-math* true)

(defmacro iloop [[b t n] & body]
  `(loop [~@b]
     (when ~t
       ~@body
       (recur ~n))))

(defn count-primes [^long n]
  (let [c (inc n)
        ^booleans prime? (make-array Boolean/TYPE c)]
    (iloop [(i 2) (<= i n) (inc i)]
      (aset prime? i true))
    (iloop [(i 2) (<= (* i i) n) (inc i)]
      (if (aget prime? i)
        (iloop [(j i) (<= (* i j) n) (inc j)]
          (aset prime? (* i j) false))))
    (areduce prime? i r 0
      (if (aget prime? i)
        (inc r)
        r))))

heh, yeah thanks.

Thanks for the great post. I can follow everything but the "[Z" bit... ^"[Z" assigns the metadata {:tag "[Z"} to prime?, correct? What does the compiler do with that metadata?

Nice post!

The use of Java BitSets can further improve performance (30 % on my system):

https://gist.github.com/964676/b26344d3d09dcf66ea66000ec207751aa61bd9e3