[Haskell-cafe] A tale of Project Euler

[Andrew Coppin]

Brent Yorgey wrote:
> The algorithm you use to compute primes is actually quite inefficient, 
> and in particular, it is NOT the same algorithm that the C program is 
> using, despite first appearances!  The call to 'filter' in the sieve 
> function works by checking *every* number for divisibility by p, and 
> only keeping those that aren't divisible by p; whereas the C program 
> simply marks multiples of p as non-prime, skipping over those which 
> are not multiples.  So the Haskell version basically searches for 
> primes by doing trial division on every single integer, whereas the C 
> version is actually using a sieve.

I had to reread that several times to figure out what you're actually 
saying.

So the Haskell version tests all N elements to see if P divides them, 
whereas the C version loops over an array (roughly) N / P times flagging 
the composite numbers, which is why it's so much damn faster. (Since as 
P grows, N / P plummets.)

OK, cool. So... now how do I implement this without using mutable 
arrays? :-}

PS. The *original* prime number thing I had was much slower. Used an 
"is_prime" function to do trial division by *every* number below N. (!!) 
The version I showed as much faster than that, but still quite slow, as 
you say...