Prime number generator

[Joshua Landau]

On 10 July 2013 15:00, 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?

Of course there is.

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

Of course it can.

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

Of course there is. I have no clue what, though.

> And finally, whose wheel
> did I reinvent here?

Mine :P. That just proves the algorithm is older still, though. You
also did it much more neatly and much more slowly, though. The trick
is to avoid that repeated effort of finding the minimum in the dict by
just keeping a sorted list.

I've mocked that up just now:

# Faster code #
from blist import sortedlist

def generate_primes():
    primes = sortedlist()
    primes.add([4, 2])

    yield 2
    i = 3

    while True:
        next_nonprime, prime_factor = primes.pop(0)

        for prime in range(i, next_nonprime):
            yield prime
            primes.add([prime*2, prime])

        i = next_nonprime + 1

        primes.add([next_nonprime + prime_factor, prime_factor])
# No longer code #

> What name would this algorithm have?

I'll call it "the flamingo".

> 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 generate_primes():
        """Generate an infinite series of prime numbers."""
        i = 2
        yield 2

        primes = {2:2} # Map a prime number to its next composite (but
bootstrap with 2:2)
        while True:
                prm = min(primes, key=primes.__getitem__)
                smallest = primes[prm]

                primes[prm] += prm

                for prm in range(i, smallest):
                        yield prm
                        primes[i] = 2*i

                i = smallest + 1

gen=generate_primes()
for i in range(30):
        print(next(gen),end="\t") # Star Trek?
print()
> # -- end --