[Haskell-cafe] how to make haskell faster than python at finding primes?

Vimal j.vimal at gmail.com
Mon Aug 6 05:35:51 EDT 2007


> Isn't it how it runs  ? :
>
> 2: sieve [3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,
> 47,49,... ]
> then
> 2:3:sieve [5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,... ]
> then
> 2:3:5:sieve [7,11,13,17,19,23,29,31,37,41,43,47,49,... ]
> then
> 2:3:5:7:sieve [11,13,17,19,23,29,31,37,41,43,47,... ]
> then
> 2:3:5:7:11:sieve [13,17,19,23,29,31,37,41,43,47,... ]
> etc...
>

Well well, see how the values are requested for:
print (take 1000 primes)
So, after sieve completes its action, the first 1000 elements are
taken. Since Haskell
is lazy, it doesnt do beyond 1000.

I would expect your argument to hold good for something like this:

primes n = sieve (take n [2..])
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p > 0]
print (primes 1000)

-- Vimal


More information about the Haskell-Cafe mailing list