The Dig Deeper tab for the Sieve exercise in Rust offers two approaches. I believe there’s a slight error in the “Ranges and filter-map()” solution.
The second range starts at prime + prime, but it can actually start at prime * prime (because any smaller multiples of prime have already been marked as None in previous iterations of the outer Range).
Of course, prime + prime will still produce the correct result, but it does unnecessary work.
(If I’m correct, then some text in the detailed explanation of this approach also needs to change: the inner range starts at “the element value times itself”, not “the element value plus itself”.)
The sieve algorithm is defined by starting at the first multiple of the prime. Which is prime + prime. The squaring is an optimization that is not part of the sieve algorithm. So I wouldn’t see that as an error, it is a possible optimization not done.
@mk-mxp thank you. The thing is that the other approach already does this optimization. So whatever we do, I think it makes sense for the two approaches to be consistent. Do you think both should be prime + prime? I think it’s fine to forgo micro-optimizations if it helps with the clarity of the algorithm.
I’m not very experienced with Approaches. Maybe it is a good thing to add an “Optimizations” chapter. To stop at the square root of the upper limit is an optimization as well. Both optimizations may make it more difficult to see the own approach vs. the discussed ones.
It looks like you’ve made the change I suggested – thanks!
I can see mk-mxp’s point but, personally, I find it much more helpful when featured solutions include “easy” optimizations: if I didn’t use them in my own solution, I want to know about them; if I did use them in my solution but they’re absent from the sample solution, I can end up second-guessing myself unnecessarily.