[Edu-sig] Pythonic Math must include...

[Andre Roberge]

On Sun, Jan 18, 2009 at 7:31 PM, Gregor Lingl <gregor.lingl at aon.at> wrote:
[SNIP]

> ======================================================
>
> Summing up:
>
> Kirby                          1.71 s                  42.72 s
> Michel Paul                    1.58 s                  32.25 s
> Michel Paul modified::         0.14 s                   1.05 s
> Scott Daniels:                 0.07 s                   0.50 s
> G.L. minimal sieve:            0.014 s                  0.109 s
> G.L. sieve:                    0.012 s                  0.086 s
> G.L. sieve-based generator:    0.023 s                  0.113 s
> (performance depends on CHUNKSIZE)
>

You may also want to consider the following:

'''
Sieve of erathosthenes, from the Python Cookbook, 2nd edition

'''

import itertools
import pprint

def erathosthenes():
    '''Yields the sequence of prime numbers via the Sieve of Erathosthenes.'''
    D = {}  # map each composite integer to its first-found prime factor
    for q in itertools.count(2): # q gets 2, 3, 4, 5, ... ad infinitum
        p = D.pop(q, None)
        if p is None:
            # q not a key in D, so q is a prime, therefore, yield it
            yield q
            # mark q square as not-prime (with q as first found prime factor)
            D[q*q] = q
            if __name__ == '__main__':
                pprint.pprint(D)
        else:
            # q is a composite number with p as its first-found prime number
            # So, let's try to find the next smallest possible composite to
            # add and that was not already present with the same first-found
            # prime number
            x = q + p
            while x in D:
                x += p
            D[x] = p

if __name__ == '__main__':
    sieve = erathosthenes()
    for i in range(10):
        print sieve.next()



===
André