[Haskell-beginners] Efficient sieve of erastothenes,
for solving project euler problem #10?
Kurt Hutchinson
kelanslists at gmail.com
Mon Nov 24 09:56:33 EST 2008
On Sun, Nov 23, 2008 at 5:28 PM, Malcolm Reynolds
<malcolm.reynolds at gmail.com> wrote:
> Hello all,
>
> I'm attempting to learn Haskell by going through the project euler
> problems. Number 10,
> http://projecteuler.net/index.php?section=problems&id=10 , involves
> summing prime numbers. It's easy in terms of coding something up that
> works, but I'm having a lot of trouble getting decent performance.
I realize that these early prime number related Euler problems are
about writing your own efficient prime generator, so you may want to
ignore this message for now. But later on when the problems just
happen to involve primes, but the generator is kind of assumed, you
may want to check out this collection:
http://www.cs.hmc.edu/~oneill/code/haskell-primes.zip
The file "ONeillPrimes.hs" contains what is, I think, generally
considered to be one of the fastest pure-Haskell prime generators. In
particular, this program:
> import ONeillPrimes ( primesToLimit )
>
> main = ( print . sum . primesToLimit ) 2000000
Gives the correct answer on my machine in about 0.3 seconds.
More information about the Beginners
mailing list