Skip to content

Instantly share code, notes, and snippets.

@bitops
Created December 29, 2011 11:50
Show Gist options
  • Save bitops/1533726 to your computer and use it in GitHub Desktop.
Save bitops/1533726 to your computer and use it in GitHub Desktop.
Rich Hickey's Prime number sieve using Java Interop
;; from http://paste.lisp.org/display/69952
(defn sieve [n]
(let [n (int n)]
"Returns a list of all primes from 2 to n"
(let [root (int (Math/round (Math/floor (Math/sqrt n))))]
(loop [i (int 3)
a (int-array n)
result (list 2)]
(if (>= i n)
(reverse result)
(recur (+ i (int 2))
(if (< i root)
(loop [arr a
inc (+ i i)
j (* i i)]
(if (>= j n)
arr
(recur (do (aset arr j (int 1)) arr)
inc
(+ j inc))))
a)
(if (zero? (aget a i))
(conj result i)
result)))))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment