[Haskell-beginners] Performance of Prime Generator
es at ertes.de
Sat Jan 21 23:18:23 CET 2012
Zhi-Qiang Lei <zhiqiang.lei at gmail.com> wrote:
> Well, thanks, so far I have tried wheel only and Sieve of Eratosthenes
> only approaches. They both failed. When the numbers is between
> 999900000 and 1000000000, they can take more than a hour on my laptop.
Indeed, you're right. The method is too slow for numbers of that scale.
I suggest trying the Sieve of Atkin, which performs quadratically faster
than the Sieve of Eratosthenes.
I haven't tried it, but an equivalent C implementation can easily
compute the first 10^9 prime numbers within seconds.
nightmare = unsafePerformIO (getWrongWife >>= sex)
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 836 bytes
Desc: not available
More information about the Beginners