[Haskell-beginners] Performance of Prime Generator

Burton Samograd burton.samograd at gmail.com
Mon Jan 23 16:30:45 CET 2012

Zhi-Qiang Lei <zhiqiang.lei at gmail.com> writes:
> 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.

There are some pretty good examples of fast prime generators here:


although using them for SPOJ is a bit like cheating :)  I learned a lot
from that page though, so I advise giving it a good readover.

Burton Samograd

More information about the Beginners mailing list