[Haskell-beginners] Performance of Prime Generator

[Zhi-Qiang Lei]

Hi, what do you mean "more naive wheel trial division"?

On Jan 21, 2012, at 5:44 PM, Ertugrul Söylemez wrote:

> 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/
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners