Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
sieve.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))))
@swannodette
Copy link
Author

swannodette commented May 9, 2011

heh, yeah thanks.

@ejconlon
Copy link

ejconlon commented May 10, 2011

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?

@juergenhoetzel
Copy link

juergenhoetzel commented May 10, 2011

Nice post!

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

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment