<div>You might want to start with the Sieve of Atkin:</div>
<div> </div>
<div><a href="http://en.wikipedia.org/wiki/Sieve_of_Atkin">http://en.wikipedia.org/wiki/Sieve_of_Atkin</a><br><br>-Edward</div>
<div> </div>
<div class="gmail_quote">On Tue, Apr 14, 2009 at 8:40 AM, Niemeijer, R.A. <span dir="ltr"><<a href="mailto:r.a.niemeijer@tue.nl">r.a.niemeijer@tue.nl</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">
<div lang="EN-US" vlink="purple" link="blue">
<div>
<p>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 (<a href="http://www.haskell.org/haskellwiki/Prime_numbers" target="_blank">http://www.haskell.org/haskellwiki/Prime_numbers</a>) has a number of implementations, but the faster they get, the longer and uglier they become.</p>
<p> </p>
<p>Since it’s such a common problem I’d say it would be a good idea to add a package to Hackage that exports</p>
<p>primes :: [Integer]</p>
<p>and hides the ugly implementation details. Data.Numbers.Primes seems a logical choice for the namespace, but I’m open to suggestions.</p>
<p> </p>
<p>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?</p>
</div></div><br>_______________________________________________<br>Haskell-Cafe mailing list<br><a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br><a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br>