Prime number generator

[Chris Angelico]

On Thu, Jul 11, 2013 at 2:01 AM, Steven D'Aprano
<steve+comp.lang.python at pearwood.info> wrote:
> On Thu, 11 Jul 2013 00:00:59 +1000, Chris Angelico wrote:
>> Thirdly, is there any sort of half-sane benchmark that I
>> can compare this code to? And finally, whose wheel did I reinvent here?
>> What name would this algorithm have?
>
> I can't directly answer that question, but I can make a shameless plug
> for this:
>
> https://pypi.python.org/pypi/pyprimes
>
> If your prime generator performs better than, or worse than, all of those
> in the above module, I may have to steal it from you :-)

Ha, that's what I was hoping for. My algorithm outperforms several of
yours! Look!

Rosuav: 0.10868923284942639
awful_primes: 16.55546780386893
naive_primes1: 2.6105180965737276
naive_primes2: 1.358270674066116
trial_division: 0.06926075800136644
turner: 0.5736550315752424
croft: 0.007141969160883832
sieve: 0.01786707528470899
cookbook: 0.014790147909859996
wheel: 0.015050236831779529

Okay, so I outperform only algorithms listed as toys... :| Here's
similar figures, going to a higher cutoff (I kept it low for the sake
of awful_primes) and using only the algos designed for real use:

Rosuav: 2.1318494389650082
croft: 0.11628042111497416
sieve: 0.26868582459502566
cookbook: 0.21551174800149164
wheel: 0.4761577239565362

I didn't seriously think that this would outperform mathematically
proven and efficient algorithms, it was just a toy. But at least now I
know: It's roughly 20 times slower than a leading algo. And that's
after the bas-suggested improvement of using a heap.

But hey. If you want the code, you're welcome to it - same with anyone
else. Here's the heap version as used in the above timings. MIT
license.

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))
		if i<smallest:
			yield i
			heappush(prime, (i+i, i))
			i+=1
		if i==smallest: i+=1
# ----

Enjoy!

ChrisA