On Thu, Jul 11, 2013 at 1:43 AM, Joshua Landau <jos...@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
--
http://mail.python.org/mailman/listinfo/python-list
