Prime number generator

[Albert van der Horst]

In article <mailman.4522.1373464867.3114.python-list at python.org>,
Chris Angelico  <rosuav at gmail.com> wrote:
>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?

Notice that all values from i on are possibly present.
So you are better off with a list indexed by forthcoming i's and
each item containing a list of primes. What you do then, more or less,
is keep track of all dividers of primes to be.
This promises to be reasonable efficient.
I've done a similar thing in Forth.

I've also done a slightly different but related parallel program on a
multi-processor Forth machine where each processor takes care of one
prime.

There is an unpleasant fact about this kind of generators.
If you want to go unbounded, you've no choice but remember all
primes. If you go bounded, you need to remember 168 up til 1M,
say sqrt(limit)/log(limit). This dramatic difference (and the lack
of processors) leads one quickly to decide for some upper bound.

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

I had problems with the print statement on a 2 version, fixed easy
enough.

>
>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 --
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert at spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst