Hi Melissa, You 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. I tried to get her to use my way of deciding what is the next multiple. Then she could do something a little more like what you are saying by using the layout of the sieve to jump ahead more quickly to the next multiple. But she insists on using apfelmus' way.
- Eratosthenes's sieve crosses-off/looks-at 459 (i.e., 17 * 27), even though we crossed it off already when we crossed off multiples of 3 -- whether you call that crossing it off a second time, or merely stepping over it, it still needs to alight on 459 to get to 493 (17 * 29), which hasn't been crossed off yet
True, the deleteOrd algorithm has that extra optimization. So I guess my sieve is actually: crossOff :: Ord a => [a] -> [Either a a] -> [Either a a] crossOff xs@(x:xs') ys@(y:ys') | x < y' = crossOff xs' ys | x > y' = y : crossOff xs ys' | otherwise = Left y' : crossOff xs' ys' where y' = fromEither y crossOff _ y = y sieve (Right x:xs) = Right x : sieve (crossOff [x+x,x+x+x..] xs) sieve (Left x:xs) = Left x : sieve xs primes = catRights $ sieve $ map Right [2..] fromEither = either id id catRights :: [Either a b] -> [b] catRights (Right x:xs) = x : catRights xs catRights ( _:xs) = catRights xs catRights _ = [] That is the Sieve of Yitzchak. My daughter is using the Sieve of Apfelmus. I guess you can still claim that neither is the Sieve of Eratosthenes. Regards, Yitz