Daniel Fischer
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.
They shouldn't. But you have to use the right data structures.
For a prime sieve, you need unboxed mutable arrays if you want it to be fast. You can use STUArrays from Data.Array.ST or mutable unboxed vectors from Data.Vector.Mutable.Unboxed.
That's what I've used. You find the code on hpaste [1]. It's a carefully optimized Sieve of Eratosthenes and needs around 20 seconds for the primes up to 10^9. See the refinement in the annotation, which I've added just now. Before that it took around 35 seconds. I considered that to be "too slow". [1] http://hpaste.org/56866
I haven't tried it, but an equivalent C implementation can easily compute the first 10^9 prime numbers within seconds.
You mean the primes up to 10^9 here?
Yes, sorry. And I was referring to the Sieve of Atkin there, but you are right. That one is only slightly faster. Greets, Ertugrul -- nightmare = unsafePerformIO (getWrongWife >>= sex) http://ertes.de/