Prime number generator

[Ian Kelly]

On Tue, Jul 30, 2013 at 4:58 AM, Albert van der Horst
<albert at spenarnc.xs4all.nl> 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
around.

> 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
O(sqrt(N)).