Meikel, while the end result is the same, the time complexity of the algorithm is definately not. The exact difference is calculated in Melissa E. O'Neill's paper, "The Genuine Sieve of Eratosthenes" [1], which also includes some highly performant implementations of incremental SoE-like prime number generators in Haskell. (A highly entertaining paper, by the way. :-))
The most basic thing to note is that the SoE requires no arithmetic operations other than addition... Trial division requires repeated computations of remainder, which end up being quite expensive asymptotically. I've had a go at implementing an incremental SoE-like sieve in Clojure: http://gist.github.com/287986 It uses transients and appears to be quite a lot faster than the clojure.contrib.lazy-seq/primes implementation, although regrettably nowhere near as fast as the straightforward implementation of the same thing in Python... :-( (See [2] for a super-optimised Python version.) The version which is not using transients is slower, and to a really spectacular degree at that -- I wonder if that's one case of a programme spending more time in GC than on the actual computation at hand. Sincerely, Michal [1] www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf [2] http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/2068412#2068412 -- 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
