Prime number generator

[Chris Angelico]

On Thu, Jul 11, 2013 at 1:47 AM, bas <blswinkels at gmail.com> wrote:
> 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.

Ehh, speed isn't the ultimate. I was just trying to avoid something
that worked out ridiculously slow (a Python function call IS quite
slow). I haven't profiled the code to find out where the bulk of the
time is spent, but switching in the lambda-based version doubled total
run time, so I didn't like it :)

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

Ahh, that's the bit I should have thought of! Of course.

My original thought experiment had involved basically a really long
list, like the classic Sieve but getting longer as time moves on, with
composites replaced by None and primes with their next-markers, which
I then collapsed to a dict. Always I was thinking in terms of indexing
with the prime to get its next composite. Here's the code involving
heapq:

# -- start --
def primes():
	"""Generate an infinite series of prime numbers."""
	from heapq import heappush,heappop
	i=2
	yield 2
	prime=[(2,2)] # Heap
	while True:
		smallest, prm = heappop(prime)
		heappush(prime, (smallest+prm, prm))
		while i<smallest:
			yield i
			heappush(prime, (i+i, i))
			i+=1
		if i==smallest: i+=1

gen=primes()
print([next(gen) for i in range(10)])
for i in range(1000):
	next(gen) # Star Trek?
print("The next prime number is:",next(gen))
# -- end --

And that's significantly shorter, clearer, AND faster than the original. Thanks!

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

Ah, good point. Again, I originally was starting from 1, so the while
loop was necessary to catch 2 and 3 in the first run. When I changed
it to start at 2 and explicitly yield it first, I didn't notice to
change that.

It works correctly with the smallest multiple appearing twice because
it won't yield primes until the smallest value is higher than the
current next-prime. So when it's just yielded 11, for instance, both
the 2 and 3 slots hold 12; advancing one of those does nothing,
advancing the other allows the bottom loop to notice that 13 is now
lower than the minimum value (which will then be 14).

ChrisA