And now for something completely different.
I knocked together a prime number generator, just for the fun of it,
that works like a Sieve of Eratosthenes but unbounded. It keeps track
of all known primes and the "next composite" that it will produce -
for instance, after yielding 13, the prime map will be {2: 20, 3: 18,
5: 20, 7: 21, 11: 22, 13: 26}, each one mapped to the first multiple
greater than 13.
Notable in the algorithm is an entire lack of division, or even
multiplication. Everything is done with addition.
So, a few questions. Firstly, is there a stdlib way to find the key
with the lowest corresponding value? In the above map, it would return
3, because 18 is the lowest value in the list. I want to do this with
a single pass over the dictionary. Secondly, can the "while
i<smallest... i+=1" loop become a for...range? It's almost asking for
it, but not quite there. Thirdly, is there any sort of half-sane
benchmark that I can compare this code to? And finally, whose wheel
did I reinvent here? What name would this algorithm have?
Code tested on Python 3.3, would probably run fine on pretty much any
Python that supports yield, though I don't have a Py2.2 to test from
__future__ import generators on!
ChrisA
# -- start --
def primes():
"""Generate an infinite series of prime numbers."""
i=2
yield 2
prime={2:2} # Map a prime number to its next composite (but bootstrap
with 2:2)
while True:
# Find the smallest value in prime[] and its key.
# Is there a standard library way to do this??
# (If two values are equal smallest, either can be returned.)
prm=None
for p,val in prime.items():
if prm is None or val<smallest:
prm,smallest=p,val
prime[prm]+=prm
while i<smallest:
yield i
prime[i]=i+i
i+=1
if i==smallest: i+=1
gen=primes()
for i in range(30):
print(next(gen),end="\t") # Star Trek?
print()
# -- end --
--
http://mail.python.org/mailman/listinfo/python-list
