# [Edu-sig] Kirby Urner's Sieve of Eratosthenes

Kirby Urner pdx4d@teleport.com
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.
>
>Kirby

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
this question.

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().

Kirby

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:

def sum(terms):
"""Same as SIGMA (terms is a list)"""

def product(terms):
"""Same as PI (terms is a list)"""
return reduce(mul,terms)

Would these be useful as "math through programming"
Python definitions?

Note: n! would be the same as product( range(1,n+1) ).

```