[Haskell-beginners] Performance of Prime Generator

Ertugrul Söylemez 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.


Greets,
Ertugrul

-- 
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://ertes.de/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120121/2497bdd5/attachment.pgp>


More information about the Beginners mailing list