[Haskell-cafe] how to make haskell faster than python at finding
primes?
Vimal
j.vimal at gmail.com
Mon Aug 6 05:09:38 EDT 2007
>
> Why not just:
>
> primes = sieve [2..]
>
> sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0]
>
> main = print (take 1000 primes)
>
I am unable to see how exactly this will run. Given that primes is an infinite
list, and that when it reaches numbers say, as large as 10000, it will have to
keep track of all the numbers (essentially prime numbers, which is the answer),
whose mutliples it has to remove!
Say for eg: I give
> take 100 primes
2 : [ 3...]
then 2:3:[4 ... ]
It will *now* have to remove 4,
2:3:[5...]
Then 2:3:5:[6 ...]
Now. It has to remove 6, based on the fact that it was a multiple of 2 ...
(or 3? Which one comes first?)
This happens in a different order than what would be expected
generally in a sieve :-)
So, the question is, does this improve efficiency?
-- Vimal
More information about the Haskell-Cafe
mailing list