C

#### Chris Angelico

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+=1

if i==smallest: i+=1

gen=primes()

for i in range(30):

print(next(gen),end="\t") # Star Trek?

print()

# -- end --

i+=1

if i==smallest: i+=1

gen=primes()

for i in range(30):

print(next(gen),end="\t") # Star Trek?

print()

# -- end --