Fast Prime Number Generation in Clojure

by

Here’s another approach that celebrates Clojure's Java interop. This takes 374ms on a 2.4 Ghz Core 2 Duo (running single-threaded). I let the efficient Miller-Rabin implementation in Java’s BigInteger#isProbablePrime deal with the primality check.

(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 Miller-Rabin certainty of 5 is probably not very good for numbers much larger than this. That certainty is equal to 96.875% certain it’s prime (1 - .5^certainty)

More Related Contents:

  1. Why exactly is eval evil?
  2. What is the difference between Lisp-1 and Lisp-2?
  3. How Are Lazy Sequences Implemented in Clojure?
  4. How many primitives does it take to build a LISP machine? Ten, seven or five?
  5. Clojure – Combining Two vectors into a vector of vectors [duplicate]
  6. Recursive function causing a stack overflow
  7. How to handle java variable length arguments in clojure?
  8. Difference between doseq and for in Clojure
  9. conda, condi, conde, condu
  10. Clojure: reduce vs. apply
  11. How to compare two functions for equivalence, as in (λx.2*x) == (λx.x+x)?
  12. What is zip (functional programming?)
  13. Idiomatic clojure map lookup by keyword
  14. Matrix transposition in clojure
  15. difference between use and require
  16. How do I avoid Clojure’s chunking behavior for lazy seqs that I want to short circuit?
  17. How do I find the index of an item in a vector?
  18. What do Clojure symbols do when used as functions?
  19. How to convert lazy sequence to non-lazy in Clojure
  20. How to list the functions of a namespace?
  21. Producer consumer with qualifications
  22. Wrong number of args (0) passed to: PersistentVector on loop/recur function
  23. Why does using keywords or symbols as functions to lookup values from maps work?
  24. Constructing a map on anonymous function in Clojure
  25. Clojure multimethods vs. protocols
  26. Function call in -> threading macro
  27. Why such implementation of partial in clojure.core
  28. Clojure binding of dynamic var not working as expected
  29. Difference between Symbols and Vars in Clojure
  30. What is the clojure equivalent of the Python idiom “if __name__ == ‘__main__'”?

Leave a Comment