[Haskell-beginners] Performance of Prime Generator

[Ertugrul Söylemez]

Zhi-Qiang Lei <zhiqiang.lei at gmail.com> wrote:

> I have bungled the Prime Generator on SPOJ for many times. Although
> the program is faster and faster on my machine, but it keeps "time
> limited exceeded" on SPOJ (6 seconds limit). Now my approach is for
> every number in the range, check if it is prime by checking if can be
> divided by all the primes smaller than or equal its square root. For
> the numbers between 999900000 and 1000000000, it take 0.64 seconds on
> my laptop. Could anyone give me some hints to enhance it? Thanks.

Although intuitively that sounds like a great idea, in practice it's
not.  To quickly generate a large number of small primes you should
either use a sieve or use the more naive wheel trial division.  This is
for small numbers up to perhaps 2^18 or 2^20, where this method is
feasible and usually fastest.


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/4a1cd7be/attachment.pgp>