[Haskell-cafe] RE: [Announce] primes

Niemeijer, R.A. r.a.niemeijer at tue.nl
Thu Apr 16 10:45:59 EDT 2009

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.

More information about the Haskell-Cafe mailing list