Prime number generator

[Chris Angelico]

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 --