On Nov 6, 7:57 pm, Ken Wesson <kwess...@gmail.com> wrote:
> Here's a Clojure sieve that works fine up to at least 50
> million and is reasonably fast (though the same algorithm implemented
> in Java is 10x faster even with the type hints and primitive
> arithmetic in the Clojure; not sure why).
>
> (defn primes-to [n]
> (let [#^booleans sieve (boolean-array (inc n) true)
> n (int n)]
> (loop [p (int 2)]
> (let [pp (unchecked-multiply p p)]
> (if (> pp n)
> (filter identity (map #(if %1 %2) (drop 2 sieve) (iterate inc 2)))
> (do
> (loop [i pp]
> (aset sieve i false)
> (let [j (unchecked-add i p)]
> (if (<= j n)
> (recur j))))
> (let [q (int
> (loop [p (unchecked-inc p)]
> (if (aget sieve p)
> p
> (recur (unchecked-inc p)))))]
> (recur q))))))))
Returning a lazy seq doesn't seem to make much sense here,
especially since (map ... (drop 2 sieve)) holds onto the
sieve array. Returning a vector instead drops the runtime
of (time (count (primes-to 10000000))) from 5.3 s to 0.5 s
on my machine:
(loop [r (transient [2])
i 3]
(if (>= i n)
(persistent! r)
(recur
(if (aget sieve i)
(conj! r i)
r)
(+ 2 i))))
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
