Yitzchak Gale wrote:
Melissa O'Neill wrote:
- Eratosthenes's sieve never says the equivalent of, "Hmm, I wonder if 19 is a multiple of 17" -- but both the basic "sieve" we began with and the deleteOrd version do
So then maybe I taught my daughter the wrong thing. When she does 17, she moves ahead one number at a time. When she gets to a multiple of 17, she crosses it off. So yes, she does consider whether 19 is a multiple of 17.
Yes, thanks Yitzchak, that's exactly the point. In order to cross off a number, one has to find it and then to cross it. The trouble comes from the fact that both notions are somewhat interchangeable. In a sense, 'deleteOrd' searches all subsequent numbers to find the next one to cross off. At the same time, it considers all subsequent numbers whether they should be crossed off or not. Melissa's priority queue walks all numbers and decides in O(log n) whether the scrutinee is the next number to be crossed. It's the 'find' part that is algorithmically expensive. The point about "Eratosthenes's sieve" is that it does not specify algorithmically how to find the next number to be crossed. It does not even define how to store (crossed) numbers, it stores them "on paper". Of course, the computer needs to know both and there is freedom of interpretation how to implement it. But I'm glad that Melissa pointed out that this implementation has to be chosen consciously. So, I argue that Yitzchak's 'deleteOrd' is a genuine "sieve of Eratosthenes". The naive 'filter (\x -> x `mod` p /= 0)' is it as well. But I agree that the latter deserves more a name like "transposed sieve of Eratosthenes". Regards, apfelmus