Prime number generator

Ian Kelly ian.g.kelly at
Tue Jul 30 19:33:46 CEST 2013

On Tue, Jul 30, 2013 at 4:58 AM, Albert van der Horst
<albert at> wrote:
> Notice that all values from i on are possibly present.
> So you are better off with a list indexed by forthcoming i's and
> each item containing a list of primes. What you do then, more or less,
> is keep track of all dividers of primes to be.
> This promises to be reasonable efficient.
> I've done a similar thing in Forth.

What do you do when you get up into the billions?  It seems
inefficient to keep a mostly empty billion-element list hanging

> There is an unpleasant fact about this kind of generators.
> If you want to go unbounded, you've no choice but remember all
> primes. If you go bounded, you need to remember 168 up til 1M,
> say sqrt(limit)/log(limit). This dramatic difference (and the lack
> of processors) leads one quickly to decide for some upper bound.

Actually, take a look at the generator that I posted in this thread,
which avoids this.  It is unbounded but gets away with only
remembering sqrt(N) primes by recursively regenerating the primes
already seen as needed.  Thus it only uses (2 * N**(1/2) + 4 *
N**(1/4) 8 * N**(1/8) + ...) / log(N) extra memory, which I believe is

More information about the Python-list mailing list