Prime number generator

[Ian Kelly]

On Wed, Jul 10, 2013 at 11:47 AM, Joshua Landau <joshua at landau.ws> wrote:
>>> 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.
>
> Actually, because it's a list under the hood I'd imagine push and pop
> still take O(n) time :/.

It shouldn't.  You can implement push by appending the new item and
then getting it into the right place by performing O(log n) swaps.
Likewise for pop, you can update the heap with O(log n) swaps and then
removing the tail element.  Appending or removing the tail element of
a list is amortized O(1).

> PS: It's faster to use heapreplace(...) than
> heappop(...);heappush(...) but it only saves a few %.

The problem with heapreplace here is that the value to be pushed
is dependent on the value returned by pop.