Prime number generator

[bas]

On Wednesday, July 10, 2013 5:12:19 PM UTC+2, Chris Angelico wrote:
> Well, that does answer the question. Unfortunately the use of lambda
> there has a severe performance cost [ ...]
If you care about speed, you might want to check the heapq module. Removing the smallest item and inserting a new item in a heap both cost O(log(N)) time, while finding the minimum in a dictionary requires iterating over the whole dictionary, which cost O(N) time.

(untested)
#before loop
from heapq import *
primes = [(2,2)] #heap of tuples (multiple, prime). start with 1 item, so no need for heapify

#during loop
smallest, prm = heappop(primes)
heappush(primes, (smallest+prm, prm))

#when new prime found
heappush(primes, (i+i, i))

> > Still trying to figure out your algorithm ...
> It's pretty simple.  [...]
I understand what you are trying, but it is not immediately clear to me that it works correctly if for example a smallest factor appears twice in the list. I don't have time for it now, but it for sure can be simplified. The while loop, for example, can be replaced by an if, since it will never execute more than once (since if i is prime > 2, i+1 will be divisible by 2)