Skip to content

Instantly share code, notes, and snippets.

@retzkek
Last active January 2, 2016 16:19
Show Gist options
  • Save retzkek/8329043 to your computer and use it in GitHub Desktop.
Save retzkek/8329043 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes using Java array
(defn eratos-array
"Compute all primes below n using Sieve of Eratosthenes. Uses Java Boolean array of odds."
[n]
(let [array (boolean-array (-> n (quot 2) (dec)) true) ;; 0=3,1=5,2=7,...
n-to-i (fn [n] (-> n (- 3) (/ 2)))
i-to-n (fn [i] (+ i i 3))]
(loop [i 3]
(if (> (* i i) n)
(areduce array ii ret [2]
(if (aget array ii)
(conj ret (i-to-n ii))
ret))
(recur (do
(doseq [j (range (+ i i) n i)]
(if (odd? j)
(aset-boolean array (n-to-i j) false)))
(+ i 2)))))))
(= (eratos-array 100) [2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment