Prime number generator
rosuav at gmail.com
Wed Jul 10 18:52:31 CEST 2013
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:
> 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
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:
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
"""Generate an infinite series of prime numbers."""
from heapq import heappush,heappop
prime=[(2,2)] # Heap
smallest, prm = heappop(prime)
heappush(prime, (smallest+prm, prm))
heappush(prime, (i+i, i))
if i==smallest: i+=1
More information about the Python-list