Hamish Grubijan Hamish Grubijan - 1 month ago 22
Python Question

How to implement an efficient infinite generator of prime numbers in Python?

This is not a homework, I am just curious.

INFINITE is the key word here.

I wish to use it as for p in primes(). I believe that this is a built-in function in Haskell.

So, the answer cannot be as naive as "Just do a Sieve".

First of all, you do not know how many consecutive primes will be consumed. Well, suppose you could concoct 100 of them at a time. Would you use the same Sieve approach as well as the frequency of prime numbers formula?

I prefer non-concurrent approach.

Thank you for reading (and writing ;) )!

Answer

I still like what I wrote up here (a Cookbook recipe with many other authors) -- it shows how a Sieve of Eratosthenes has no intrinsic limits, and the comments and discussion, I believe, make it quite clear. This was recently discussed on Stack Overflow (search for the authors' names, I guess) and somebody proposed a substantially faster (but IMHO less clear) version;-).