On Sun, Jan 18, 2009 at 7:31 PM, Gregor Lingl <gregor.li...@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é _______________________________________________ Edu-sig mailing list Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig