[Haskell-cafe] Re: Optimization fun

[DavidA]

Lennart Augustsson <lennart <at> augustsson.net> writes:

> Yes, and that's pretty much what my version does (and what the  
> original tried to do?).

Yes, you're right, I see now that my method is equivalent to yours. (My 
apologies, it was late.)

The point I was trying to make is that there are two different ways to do it. 
The sieve method works by starting with the list [2..] (or [3,5..]), and 
successively filtering it to remove multiples as we discover each new prime. So 
the list starts out as [2,3,4,5..], then goes to [3,5,7,9..], then goes to 
[5,7,11,13..]. At each stage we're removing not just first element of the list, 
but all later elements divisible by it too. (eg in the last step we removed 9 
as well as 3)

The other method is to leave the list intact, and just test each element by 
trial division as we come to it.

The point is that the trial division method is much faster than the sieve 
method. Maintaining all those filter of filter of filter of ...  lists is 
hugely inefficient.

Intuitively I can see why, but it would be nice to have a good explanation.