Re: Prime number generator

References	<mailman.4522.1373464867.3114.python-list@python.org> <51f79c4c$0$1672$e4fe514c@dreader35.news.xs4all.nl>
From	Ian Kelly <ian.g.kelly@gmail.com>
Date	2013-07-30 11:33 -0600
Subject	Re: Prime number generator
Newsgroups	comp.lang.python
Message-ID	<mailman.15.1375272465.1251.python-list@python.org> (permalink)

Show all headers | View raw

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

Back to comp.lang.python | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Prime number generator Chris Angelico <rosuav@gmail.com> - 2013-07-11 00:00 +1000
  Re: Prime number generator Bas <wegwerp@gmail.com> - 2013-07-10 07:35 -0700
    Re: Prime number generator Chris Angelico <rosuav@gmail.com> - 2013-07-11 01:12 +1000
      Re: Prime number generator bas <blswinkels@gmail.com> - 2013-07-10 08:47 -0700
        Re: Prime number generator Chris Angelico <rosuav@gmail.com> - 2013-07-11 02:15 +1000
        Re: Prime number generator Joshua Landau <joshua@landau.ws> - 2013-07-10 18:47 +0100
        Re: Prime number generator Ian Kelly <ian.g.kelly@gmail.com> - 2013-07-10 12:56 -0600
        Re: Prime number generator Joshua Landau <joshua@landau.ws> - 2013-07-10 20:06 +0100
      Re: Prime number generator bryanjugglercryptographer@yahoo.com - 2013-07-30 21:57 -0700
  Re: Prime number generator Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-10 16:01 +0000
    Re: Prime number generator Chris Angelico <rosuav@gmail.com> - 2013-07-11 02:52 +1000
  Re: Prime number generator albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-30 10:58 +0000
    Re: Prime number generator Ian Kelly <ian.g.kelly@gmail.com> - 2013-07-30 11:33 -0600

csiph-web