[Haskell-cafe] Re: Genuine Eratosthenes sieve [Was: Optimization
gale at sefer.org
Tue Feb 20 03:21:37 EST 2007
> - 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
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.
More information about the Haskell-Cafe