[Edu-sig] Kirby Urner's Sieve of Eratosthenes
Mon, 05 Jun 2000 12:07:08 -0700
>Note that my version, while not as compact in code, uses only
>addition to change 1s to 0s. Using % over range(2,limit)
>implies many divisions, and perhaps is not as fast, though
>I haven't done any work to ascertain this for a fact.
In fact, I'd go even further and say it's the essence of
the Erastosthenes method that we _do not_ try to figure
out if 13 (for example) goes evenly into some gnarly
multi-digit number -- nor should we ask the computer
In filtering out non-primes, we're just counting off, and
crossing out every 13th number, never trying to divide
anything into anything else and looking at the remainder.
So I'd say the % or mod operator really _can't_ be part
of this process -- IF we're going to call this is a
Sieve of Erastosthenes. Gotta remain faithful to the
core strategy to merit that moniker.
Trial-by-division, on the other hand, does use % (aka mod).
Again, I certainly learned from John's post and value his
contribution. I'm not a Python guru (yet) and likely
could compactify my code (without sacrificing readability)
in many methods -- including in erastosthenes().
PS: Dustin, would your agree that reduce(mul,terms) and
reduce(add,terms) are a useful way to introduce sums and
products, corresponding to geeky greek symbols capital
SIGMA and capital PI. In other words:
from operator import mul,add
"""Same as SIGMA (terms is a list)"""
"""Same as PI (terms is a list)"""
Would these be useful as "math through programming"
Note: n! would be the same as product( range(1,n+1) ).