[Haskell-cafe] Looking for the fastest Haskell primes algorithm

Eugene Kirpichov ekirpichov at gmail.com
Tue Apr 14 08:57:29 EDT 2009

I'd suggest also

primesFrom :: Integer -> [Integer]

and probably a separate function

nextPrime :: Integer -> Integer

2009/4/14 Andrew Wagner <wagner.andrew at gmail.com>:
> Some other ideas for things to put in this package possibly:
> is_prime :: Int -> Bool
> nth_prime :: Int -> Int -- or Int -> Integer
> prime_factors :: Int -> [Int]
> I'm assuming there are faster ways of doing the first 2 than by just simply
> looking through all of primes. Someone should also look through Euler - I'm
> sure that will generate other ideas of things that could be useful in
> playing with primes.
> On Tue, Apr 14, 2009 at 8:40 AM, Niemeijer, R.A. <r.a.niemeijer at 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 at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

Eugene Kirpichov
Web IR developer, market.yandex.ru

More information about the Haskell-Cafe mailing list