Prime number generator

[Chris Angelico]

On Thu, Jul 11, 2013 at 12:35 AM, Bas <wegwerp at gmail.com> wrote:
> On Wednesday, July 10, 2013 4:00:59 PM UTC+2, Chris Angelico wrote:
> [...]
>> 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.
>
> In [1]: prime = {2: 20, 3: 18, 5: 20, 7: 21, 11: 22, 13: 26}
>
> In [2]: smallest_key = min(prime.iteritems(), key=lambda k_v: k_v[1])[0]
>
> In [3]: smallest_key
> Out[3]: 3

Well, that does answer the question. Unfortunately the use of lambda
there has a severe performance cost (roughly doubles the total run
time, when I ask for the thousandth prime), without majorly improving
readability. I'll bear it in mind if there's a way to make that work
on either readability or performance, but otherwise, I'll stick with
the explicit loop. Thanks anyway!

> Still trying to figure out your algorithm ...

It's pretty simple. (That's a bad start, I know!) Like the Sieve of
Eratosthenes, it locates prime numbers, then deems every multiple of
them to be composite. Unlike the classic sieve, it does the "deem"
part in parallel. Instead of marking all the multiples of 2 first,
then picking three and marking all the multiples of 3, then 5, etc,
this function records the fact that it's up to (say) 42 in marking
multiples of 2, and then when it comes to check if 43 is prime or not,
it moves to the next multiple of 2. This requires memory to store the
previously-known primes, similarly to other methods, but needs no
multiplication or division.

ChrisA