Am Donnerstag 16 April 2009 16:45:59 schrieb Niemeijer, R.A.:
Sebastian Fischer wrote:
I am pleased to announce the package 'primes' that implements lazy wheel sieves for efficient, purely functional generation of prime numbers in Haskell.
The implementation is reasonably efficient. The query
primes !! 1000000
15485867
answers after a few seconds.
Feel free to contribute more functionality to this package. The sources are on Github:
http://github.com/sebfisch/primes
If you fork my project, I'll be happy to merge your changes.
I have just finished benchmarking all the implementations provided in http://www.cs.hmc.edu/~oneill/code/haskell-primes.zip (the zip file linked to from the Haskell wiki article on primes).
NaurPrimes.hs is by far the fastest version, and at least 2 or 3 times faster than your current implementation. I'm pretty sure it also uses less memory. I want to find efficient algorithms for the other proposed functions before forking, but I figured I'd let you know in the meantime.
Nevertheless, a bitsieve is much faster: Prelude NaurPrimes> length $ primesToLimit (10^8) 5761455 (26.50 secs, 5734921092 bytes) Prelude NaurPrimes> :l Ok, modules loaded: none. (0.00 secs, 0 bytes) Prelude> :m +Euler.Primes Prelude Euler.Primes> length $ primesUpTo (10^8) Loading package base-3.0.3.0 ... linking ... done. Loading package euler-0.1 ... linking ... done. 5761455 (2.14 secs, 573050276 bytes) The problems for a bitsieve are a) you don't easily get the small primes before sieving is complete b) how to proceed after the sieving bound