I like tinkering with prime sieve algorithms.
Here's the fastest one I've come up with:
(defn bit-sieve [n]
(let [n (int n)]
"Returns a vector of all primes from 2 to n (not including n)"
(let [root (int (Math/round (Math/floor (Math/sqrt n))))]
(loop [i (int 3)
a (java.util.BitSet. n)
result (transient [2])]
(if (>= i n)
(persistent! result)
(recur (+ i (int 2))
(if (and (not (.get a i)) (<= i root))
(loop [arr a
inc (+ i i)
j (* i i)]
(if (>= j n)
arr
(recur (do (.set arr j) arr)
inc
(+ j inc))))
a)
(if-not (.get a i)
(conj! result i)
result)))))))
Also, here's an implementation of the lazy prime stream algorithm at:
http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
(defn- wheel2357 [] (cycle [2 4 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 2 4 2 4 8
6 4 6 2 4 6 2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10]))
(defn- spin [l n] (lazy-seq (cons n (spin (rest l) (+ n (first l))))))
(defn- insert-prime [p xs table]
(update-in table [(* p p)] #(conj % (map (fn [n] (* n p)) xs))))
(defn- reinsert [table x table-x]
(loop [m (dissoc table x), elems table-x]
(if-let [elems (seq elems)]
(let [elem (first elems)]
(recur (update-in m [(first elem)] #(conj % (rest elem))) (rest elems)))
m)))
(defn- adjust [x table]
(let [nextTable (first table),
n (nextTable 0)]
(if (<= n x) (recur x (reinsert table n (nextTable 1)))
table)))
(defn- sieve-helper [s table]
(when-let [ss (seq s)]
(let [x (first ss), xs (rest ss),
nextTable (first table),
nextComposite (nextTable 0)]
(if (> nextComposite x)
(lazy-seq (cons x (sieve-helper xs (insert-prime x xs table))))
(recur xs (adjust x table))))))
(defn- sieve [s]
(when-let [ss (seq s)]
(let [x (first ss), xs (rest ss)]
(cons x (sieve-helper xs (insert-prime x xs
(sorted-map)))))))
(defn prime-seq
"(prime-seq) creates a lazy stream of all positive prime numbers"
[]
(concat [2 3 5 7] (sieve (spin (wheel2357) 11))))
(def primes (prime-seq))
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
