[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.

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


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

def sum(terms):
   """Same as SIGMA (terms is a list)"""
   return reduce(add,terms)

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