Re: [Haskell-beginners] Performance of Prime Generator

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 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@haskell.org http://www.haskell.org/mailman/listinfo/beginners