Prime number generator

[Chris Angelico]

On Thu, Jul 11, 2013 at 1:43 AM, Joshua Landau <joshua at landau.ws> wrote:
>> So, a few questions. Firstly, is there...
> Of course there is.
>
>> Secondly, can the...
> Of course it can.
>
>> Thirdly, is there...
> Of course there is. I have no clue what, though.

Heh, I guess I was asking for that kind of response :)

> 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

Hmm, blist isn't part of the standard library, so I'd have to hunt
that down. Presumably it's on PyPI.

>> What name would this algorithm have?
> I'll call it "the flamingo".

Guess that's as good a name as any!

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

And once again, a version that's slower than the original. This one
does at least have the advantage of readability, though, and it's only
a little slower, so I'd say this is the current winner. I would still
replace 2*i with i+i for the sake of boasting "no multiplication",
though :)

In terms of the "one pass" criterion I put on the find-smallest
algorithm, I had been seeking to avoid anything that involved constant
lookups into primes[]. But this solution does look very clean and
simple. I think.

ChrisA