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

[John Posner]

Hi --

I don't know if anyone else has commented on the Sieve of Eratosthenes
implementation posted by Kirby Urner at the end of April. I put my response
on the back burner until now, so here goes ...

In my opinion, Kirby's implementation (see below) works too hard. The
critical problem is that it uses an old-fashioned LOOP to do the work
instead of using a nifty, Pythonic FILTER. After all, a SIEVE is just a kind
of FILTER.

------------------------------------------- my implementation
# construct a list of candidate whole numbers,
# using command-line argument as upper limit
import sys
limit = int(sys.argv[1])
nums = range(2, limit)

# initialize result list
primes = []

# process the candidate list until no numbers remain
while len(nums) > 0:
    # first item on list must be prime -- call it "prm"
    prm = nums[0]
    # add prime to result list
    primes.append(prm)
    # implement the sieve: filter out multiples of "prm"
    nums = filter(lambda n: n % prm > 0, nums)

# display results
print primes
-------------------------------------------

NOTE 1: For clarity, I think the long-winded forms of "while" and "lambda"
are preferable. That is:

   while len(nums) > 0:     <-- instead of -->      while nums:
   lambda n: n % prm > 0    <-- instead of -->      lambda n: n % prm

The short forms take advantage of a quirk of Python: the Boolean value TRUE
is implemented as non-zero/non-empty.

NOTE 2: My implementation is a main program, not a function. Packaging it up
as a function (say, "erat") introduces a scoping problem: when you attempt
to define the lambda function within the "erat" function, it can't see the
"erat" function's local variable "prm". Solution: use a default argument to
implement a closure, passing the "erat" function's local variable into the
scope of the labmda function (cf. "Programming Python", Mark Lutz, O'Reilly
& Associates, p. 746):

  lambda n: n % prm > 0

     ... must be replaced by ...

  lambda n, p=prm: n % p > 0

This ain't for a first implementation!



------------------------------------------- Kirby's implementation

def erastosthenes(n):
   # a prime number sieve, thanks to Erastosthenes
   # returns list of primes <= n
   cutoff = n ** 0.5         # 2nd root of n is cutoff
   sieve = [0, 0]+[1]*(n-1)  # [0 0 1 1 1...] with 1st 1 in position 2
   results = []              # empty list, will contain primes when done
   prime = 2                 # initial prime
   while prime <= cutoff:    # done when prime > 2nd root of n
      j = 2*prime            # jump to 2*prime (first multiple)
      # turn sieve elements corresponding
      # to multiples of prime from 1 to 0, up to n.
      while j <= n:
         sieve[j]=0
         j = j + prime
      # scan for a 1 in sieve beyond highest prime so far
      prime = prime + sieve[prime+1:].index(1) + 1
   # now translate remaining 1s into actual integers
   i=0
   for entry in sieve:     # step through all entries...
      if entry:            # if entry is 1 (i.e. true)
         results.append(i) # add prime to list
      i=i+1
   return results          # return list of primes

-------------------------------------------



--
John Posner, Editor           jjp@oreilly.com
O'Reilly & Associates         860-663-3147