You might want to start with the Sieve of Atkin: http://en.wikipedia.org/wiki/Sieve_of_Atkin
-Edward On Tue, Apr 14, 2009 at 8:40 AM, Niemeijer, R.A. <r.a.niemei...@tue.nl>wrote: > Today I happened to need a large list of prime numbers. Obviously this is > a well-known problem, so I figured there would be something on Hackage that > I could use. Surprisingly, there isn’t, or if there is it’s not easy to > find. Searching for prime or primes on Hackage reveals nothing. Searching > for primes on Hayoo gives Codec.Encryption.RSA.NumberTheory, but that uses > the inefficient one-liner implementation. The HaskellWiki article on primes > (http://www.haskell.org/haskellwiki/Prime_numbers) has a number of > implementations, but the faster they get, the longer and uglier they become. > > > > Since it’s such a common problem I’d say it would be a good idea to add a > package to Hackage that exports > > primes :: [Integer] > > and hides the ugly implementation details. Data.Numbers.Primes seems a > logical choice for the namespace, but I’m open to suggestions. > > > > The trick then is to find the most efficient implementation of primes. The > Haskell wiki article mentions ONeillPrimes.hs as one of the fastest ones, > but maybe there’s a faster version. So my question is: does anybody know > what the fastest Haskell algorithm for generating primes is? > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe