[Haskell-cafe] [Announce] primes

Sebastian Fischer sebf at informatik.uni-kiel.de
Thu Apr 16 09:30:36 EDT 2009


I am pleased to announce the package 'primes' that implements lazy  
wheel sieves for efficient, purely functional generation of prime  
numbers in Haskell.

Following the current discussion about primes in Haskell, I packaged  
up an implementation inspired by the papers "Lazy wheel sieves and  
spirals of primes" by Colin Runciman and "The Genuine Sieve of  
Eratosthenes" by Melissa O'Neil.

     http://hackage.haskell.org/cgi-bin/hackage-scripts/package/primes

The package does not implement all that was wished for in the  
mentioned discussion. It only exports two operations:

The global constant

     primes :: [Integer]

is an infinite list of primes and

     wheelSieve :: Int -> [Integer]

is the function used to build this list. If you are worried about the  
memory requirements of using a global constant, you can use  
`wheelSieve 6` instead of `primes`.

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.

Cheers,
Sebastian



More information about the Haskell-Cafe mailing list