Clojure Quick Primary Number Generation

Question

I worked on the Project Euler problem solving at Clojure to get better, and I have come across several times generating prime numbers. My problem is that it takes too much time. I was hoping someone could help me find an effective way to do this Clojure-y.

When I made it with my fist, I rudely forced it. It was easy to do. But calculating 10,001 primes took 2 minutes at Xeon 2.33 GHz, too long for the rules and generally too long. Here was the algorithm:

(defn next-prime-slow "Find the next prime number, checking against our already existing list" ([sofar guess] (if (not-any? #(zero? (mod guess %)) sofar) guess ; Then we have a prime (recur sofar (+ guess 2))))) ; Try again (defn find-primes-slow "Finds prime numbers, slowly" ([] (find-primes-slow 10001 [2 3])) ; How many we need, initial prime seeds ([needed sofar] (if (<= needed (count sofar)) sofar ; Found enough, we're done (recur needed (concat sofar [(next-prime-slow sofar (last sofar))]))))) 

Replacing next-prime-slow with a newer procedure that took into account some additional rules (for example, property 6n + / - 1), I was able to speed up the process by about 70 seconds.

Then I tried to make a sieve from Eratosthenes in pure Clojure. I don't think I pulled out all the errors, but I gave up because it was just too slow (even worse than the higher, I think).

 (defn clean-sieve "Clean the sieve of what we know isn't prime based" [seeds-left sieve] (if (zero? (count seeds-left)) sieve ; Nothing left to filter the list against (recur (rest seeds-left) ; The numbers we haven't checked against (filter #(> (mod % (first seeds-left)) 0) sieve)))) ; Filter out multiples (defn self-clean-sieve ; This seems to be REALLY slow "Remove the stuff in the sieve that isn't prime based on it self" ([sieve] (self-clean-sieve (rest sieve) (take 1 sieve))) ([sieve clean] (if (zero? (count sieve)) clean (let [cleaned (filter #(> (mod % (last clean)) 0) sieve)] (recur (rest cleaned) (into clean [(first cleaned)])))))) (defn find-primes "Finds prime numbers, hopefully faster" ([] (find-primes 10001 [2])) ([needed seeds] (if (>= (count seeds) needed) seeds ; We have enough (recur ; Recalculate needed (into seeds ; Stuff we've already found (let [start (last seeds) end-range (+ start 150000)] ; NOTE HERE (reverse (self-clean-sieve (clean-sieve seeds (range (inc start) end-range)))))))))) 

This is bad. It also causes a stack overflow if the number 150000 is less. This is despite the fact that I use recur. It could be my fault.

Then I tried a sieve using Java methods on Java ArrayList. It took quite a bit of time and memory.

My last attempt was to use a sieve using a Clojure hash map, inserting all the numbers into the sieve, and then separating the numbers that are not prime. In the end, he takes a list of keys, which are the primes he found. It takes about 10-12 seconds to find 10,000 primes. I am not sure that it is fully debugged. This is also recursive (using recur and loop), since I'm trying to be Lispy.

Thus, with such problems, problem 10 (summing all primes up to 2,000,000) is killing me. My fastest code found the correct answer, but it took 105 seconds, and it took me a lot of memory (I allocated 512 MB to him, so I did not have to bother with this). My other algorithms take so much time that I always ended up stopping them first.

I could use a sieve to calculate so many primes in Java or C pretty quickly and without using a lot of memory. I know that I am missing something in my Clojure / Lisp style that is causing the problem.

Is there something I'm doing really wrong? Is Clojure just slow with large sequences? After reading some of the discussions on the Euler project, people figured out the first 10,000 primes in other Lispx in less than 100 milliseconds. I understand that the JVM can slow things down, and Clojure is relatively young, but I would not expect a difference of 100 times.

Can someone explain me a quick way to calculate prime numbers in Clojure?

Answer 1

Here's another approach that Clojure Java interop notes. It takes 374 ms at 2.4 GHz Core 2 Duo (works single-threaded). I allow the efficient implementation of Miller-Rabin in Java BigInteger#isProbablePrime with compliance checking.

 (def certainty 5) (defn prime? [n] (.isProbablePrime (BigInteger/valueOf n) certainty)) (concat [2] (take 10001 (filter prime? (take-nth 2 (range 1 Integer/MAX_VALUE))))) 

The probability of Miller-Rabin 5 is probably not very good for numbers much larger than that. This certainty is equal to 96.875% defined for its simple ( 1 - .5^certainty )

Answer 2

I understand this is a very old question, but I recently ended up looking for the same thing, and the links here were not what I was looking for (as limited as possible to functional types, lazily generating ~ every ~ prime number I want),

I stumbled upon a good implementation of F # , so all credits it. I just ported this to Clojure:

 (defn gen-primes "Generates an infinite, lazy sequence of prime numbers" [] (letfn [(reinsert [table x prime] (update-in table [(+ prime x)] conj prime)) (primes-step [table d] (if-let [factors (get table d)] (recur (reduce #(reinsert %1 d %2) (dissoc table d) factors) (inc d)) (lazy-seq (cons d (primes-step (assoc table (* dd) (list d)) (inc d))))))] (primes-step {} 2))) 

Use is simple

 (take 5 (gen-primes)) 

Answer 3

It's very late to the party, but I will give an example using Java BitSets:

 (defn sieve [n] "Returns a BitSet with bits set for each prime up to n" (let [bs (new java.util.BitSet n)] (.flip bs 2 n) (doseq [i (range 4 n 2)] (.clear bs i)) (doseq [p (range 3 (Math/sqrt n))] (if (.get bs p) (doseq [q (range (* pp) n (* 2 p))] (.clear bs q)))) bs)) 

Running it on a MacBook Pro 2014 (Core i7 core), I get:

 user=> (time (do (sieve 1e6) nil)) "Elapsed time: 64.936 msecs" 

Answer 4

See the last example here: http://clojuredocs.org/clojure_core/clojure.core/lazy-seq

 ;; An example combining lazy sequences with higher order functions ;; Generate prime numbers using Eratosthenes Sieve ;; See http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ;; Note that the starting set of sieved numbers should be ;; the set of integers starting with 2 ie, (iterate inc 2) (defn sieve [s] (cons (first s) (lazy-seq (sieve (filter #(not= 0 (mod % (first s))) (rest s)))))) user=> (take 20 (sieve (iterate inc 2))) (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71) 

Answer 5

Here's a nice and simple implementation:

http://clj-me.blogspot.com/2008/06/primes.html

... but it was written for some version of Clojure version to version 1.0. See lazy_seqs in the Clojure Contrib for one that works with the current version of the language.

Answer 6

 (defn sieve [[p & rst]] ;; make sure the stack size is sufficiently large! (lazy-seq (cons p (sieve (remove #(= 0 (mod % p)) rst))))) (def primes (sieve (iterate inc 2))) 

with a stack size of 10 M, I get the 1001st number in ~ 33 seconds on a Macbook 2.1Gz.

Answer 7

So, I just started with Clojure, and yes, that's a lot on Project Euler, isn't it? I wrote a fairly simple algorithm for simple division of the trial division, but it does not fade too much before each section run becomes too slow.

So, I started again, this time using the sieve method:

 (defn clense "Walks through the sieve and nils out multiples of step" [primes step i] (if (<= i (count primes)) (recur (assoc! primes i nil) step (+ i step)) primes)) (defn sieve-step "Only works if i is >= 3" [primes i] (if (< i (count primes)) (recur (if (nil? (primes i)) primes (clense primes (* 2 i) (* ii))) (+ 2 i)) primes)) (defn prime-sieve "Returns a lazy list of all primes smaller than x" [x] (drop 2 (filter (complement nil?) (persistent! (sieve-step (clense (transient (vec (range x))) 2 4) 3))))) 

Usage and speed:

 user=> (time (do (prime-sieve 1E6) nil)) "Elapsed time: 930.881 msecs 

I am very pleased with the speed: it ends with REPL running on the 2009 MBP. This is mostly fast because I completely avoid the idiomatic Clojure and instead walk around like a monkey. It is also 4 times faster, because I use a transition vector to work on a sieve instead of remaining completely unchanged.

Edit: After several fixes / bug fixes from Will Ness, it now works much faster.

Answer 8

Here's a simple sieve in the circuit:

http://telegraphics.com.au/svn/puzzles/trunk/programming-in-scheme/primes-up-to.scm

Here's the mileage for primes up to 10000:

 #;1> (include "primes-up-to.scm") ; including primes-up-to.scm ... #;2> ,t (primes-up-to 10000) 0.238s CPU time, 0.062s GC time (major), 180013 mutations, 130/4758 GCs (major/minor) (2 3 5 7 11 13... 

Answer 9

Based on Will's comment, here is my postponed-primes request:

 (defn postponed-primes-recursive ([] (concat (list 2 3 5 7) (lazy-seq (postponed-primes-recursive {} 3 9 (rest (rest (postponed-primes-recursive))) 9)))) ([D pq ps c] (letfn [(add-composites [D xs] (loop [ax] (if (contains? D a) (recur (+ as)) (persistent! (assoc! (transient D) as)))))] (loop [DD pp qq ps ps cc] (if (not (contains? D c)) (if (< cq) (cons c (lazy-seq (postponed-primes-recursive D pq ps (+ 2 c)))) (recur (add-composites D (+ c (* 2 p)) (* 2 p)) (first ps) (* (first ps) (first ps)) (rest ps) (+ c 2))) (let [s (get D c)] (recur (add-composites (persistent! (dissoc! (transient D) c)) (+ cs) s) p q ps (+ c 2)))))))) 

Original view for comparison:

Here is my attempt to port this prime generator from Python to Clojure. The following is an infinite lazy sequence.

 (defn primes [] (letfn [(prime-help [foo bar] (loop [D foo q bar] (if (nil? (get D q)) (cons q (lazy-seq (prime-help (persistent! (assoc! (transient D) (* qq) (list q))) (inc q)))) (let [factors-of-q (get D q) key-val (interleave (map #(+ % q) factors-of-q) (map #(cons % (get D (+ % q) (list))) factors-of-q))] (recur (persistent! (dissoc! (apply assoc! (transient D) key-val) q)) (inc q))))))] (prime-help {} 2))) 

Using:

 user=> (first (primes)) 2 user=> (second (primes)) 3 user=> (nth (primes) 100) 547 user=> (take 5 (primes)) (2 3 5 7 11) user=> (time (nth (primes) 10000)) "Elapsed time: 409.052221 msecs" 104743 

edit:

A performance comparison, where postponed-primes uses the prime queue seen so far, rather than a recursive call to postponed-primes :

 user=> (def counts (list 200000 400000 600000 800000)) #'user/counts user=> (map #(time (nth (postponed-primes) %)) counts) ("Elapsed time: 1822.882 msecs" "Elapsed time: 3985.299 msecs" "Elapsed time: 6916.98 msecs" "Elapsed time: 8710.791 msecs" 2750161 5800139 8960467 12195263) user=> (map #(time (nth (postponed-primes-recursive) %)) counts) ("Elapsed time: 1776.843 msecs" "Elapsed time: 3874.125 msecs" "Elapsed time: 6092.79 msecs" "Elapsed time: 8453.017 msecs" 2750161 5800139 8960467 12195263) 

Answer 10

From: http://steloflute.tistory.com/entry/Clojure-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%A8-%EC%B5%9C%EC% A0% 81% ED% 99% 94

Using Java Array

 (defmacro loopwhile [init-symbol init whilep step & body] `(loop [~init-symbol ~init] (when ~whilep ~@body (recur (+ ~init-symbol ~step))))) (defn primesUnderb [limit] (let [p (boolean-array limit true)] (loopwhile i 2 (< i (Math/sqrt limit)) 1 (when (aget pi) (loopwhile j (* i 2) (< j limit) i (aset pj false)))) (filter #(aget p %) (range 2 limit)))) 

Usage and speed:

 user=> (time (def p (primesUnderb 1e6))) "Elapsed time: 104.065891 msecs" 

Answer 11

I just started using Clojure, so I don’t know if this is good, but here is my solution:

 (defn divides? [xi] (zero? (mod xi))) (defn factors [x] (flatten (map #(list % (/ x %)) (filter #(divides? x %) (range 1 (inc (Math/floor (Math/sqrt x)))))))) (defn prime? [x] (empty? (filter #(and divides? (not= x %) (not= 1 %)) (factors x)))) (def primes (filter prime? (range 2 java.lang.Integer/MAX_VALUE))) (defn sum-of-primes-below [n] (reduce + (take-while #(< % n) primes))) 

Answer 12

After moving on to this topic and looking for a faster alternative to existing ones, I am surprised that no one is connected with the next Christophe Grand article

 (defn primes3 [max] (let [enqueue (fn [sieve n factor] (let [m (+ n (+ factor factor))] (if (sieve m) (recur sieve m factor) (assoc sieve m factor)))) next-sieve (fn [sieve candidate] (if-let [factor (sieve candidate)] (-> sieve (dissoc candidate) (enqueue candidate factor)) (enqueue sieve candidate candidate)))] (cons 2 (vals (reduce next-sieve {} (range 3 max 2)))))) 

Like the lazy version:

 (defn lazy-primes3 [] (letfn [(enqueue [sieve n step] (let [m (+ n step)] (if (sieve m) (recur sieve m step) (assoc sieve m step)))) (next-sieve [sieve candidate] (if-let [step (sieve candidate)] (-> sieve (dissoc candidate) (enqueue candidate step)) (enqueue sieve candidate (+ candidate candidate)))) (next-primes [sieve candidate] (if (sieve candidate) (recur (next-sieve sieve candidate) (+ candidate 2)) (cons candidate (lazy-seq (next-primes (next-sieve sieve candidate) (+ candidate 2))))))] (cons 2 (lazy-seq (next-primes {} 3))))) 

Answer 13

Idiomatic and not so bad

 (def primes (cons 1 (lazy-seq (filter (fn [i] (not-any? (fn [p] (zero? (rem ip))) (take-while #(<= % (Math/sqrt i)) (rest primes)))) (drop 2 (range)))))) => #'user/primes (first (time (drop 10000 primes))) "Elapsed time: 0.023135 msecs" => 104729 

Answer 14

There are already many answers, but I have an alternative solution that generates an infinite sequence of primes. I was also interested in choosing several solutions.

First, a bit of interaction with Java. for reference:

 (defn prime-fn-1 [accuracy] (cons 2 (for [i (range) :let [prime-candidate (-> i (* 2) (+ 3))] :when (.isProbablePrime (BigInteger/valueOf prime-candidate) accuracy)] prime-candidate))) 

Benjamin @ http: //stackoverflow.com

nha @ https://stackoverflow.com>

My implementations are primes-fn-4 :

 (defn primes-fn-4 [] (let [primes-with-duplicates (->> (for [i (range)] (-> i (* 2) (+ 5))) ; 5, 7, 9, 11, ... (reductions (fn [known-primes candidate] (if (->> known-primes (take-while #(<= (* % %) candidate)) (not-any? #(-> candidate (mod %) zero?))) (conj known-primes candidate) known-primes)) [3]) ; Our initial list of known odd primes (cons [2]) ; Put in the non-odd one (map (comp first rseq)))] ; O(1) lookup of the last element of the vec "known-primes" ; Ugh, ugly de-duplication :( (->> (map #(when (not= % %2) %) primes-with-duplicates (rest primes-with-duplicates)) (remove nil?)))) 

The numbers indicated (the time in milliseconds to count the first N primes) are the fastest in series 5, the JVM does not restart between experiments, so your mileage may vary:

  1e6 3e6 (primes-fn-1 5) 808 2664 (primes-fn-1 10) 952 3198 (primes-fn-1 20) 1440 4742 (primes-fn-1 30) 1881 6030 (primes-fn-2) 1868 5922 (primes-fn-3) 489 1755 <-- WOW! (primes-fn-4) 2024 8185 

Answer 15

If you don't need a lazy solution, and you just want a sequence of primes below a certain limit, the direct implementation of Sieve of Eratosthenes is pretty fast. Here is my transient version:

 (defn classic-sieve "Returns sequence of primes less than N" [n] (loop [nums (transient (vec (range n))) i 2] (cond (> (* ii) n) (remove nil? (nnext (persistent! nums))) (nums i) (recur (loop [nums nums j (* ii)] (if (< jn) (recur (assoc! nums j nil) (+ ji)) nums)) (inc i)) :else (recur nums (inc i)))))