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

Kirby Urner pdx4d@teleport.com
Mon, 05 Jun 2000 17:27:55 -0700

Here's an ugly way to avoid lambda -- illustrative of
points made in 'Learning Python: Nested Functions
Aren't Nested Scopes' (pg 118-120):

def erastosthenes(max):  # with thanks to Ka-Ping Yee
        """Sieve of Erastosthenes"""
        global sieve  # force to module level
        sieve = [0, 0] + [1] * max
        prime = 2
        while prime*prime <= max:
            for i in range(prime * 2, max + 1, prime): 
                sieve[i] = 0
            prime = prime+1 + sieve[prime+1:].index(1)
        def final(x): return sieve[x]  # internal function
        return filter(final, range(max + 1))

Could also make

def final(x): return sieve[x] 

a top-level function and eliminate this line from inside

I'm not advocating this approach -- why we have lambda is
so we can avoid it.  Still, it's a useful example of
"learning Python through Python" (if not math).