Re: Prime number generator

Path	csiph.com!usenet.pasdenom.info!gegeweb.org!usenet-fr.net!nerim.net!novso.com!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path	<ian.g.kelly@gmail.com>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	UNSURE 0.221
X-Spam-Level	**
X-Spam-Evidence	'H': 0.57; 'S': 0.02; 'subject:number': 0.09; 'mostly': 0.14; 'posted': 0.15; 'bound.': 0.16; 'forth.': 0.16; 'generators.': 0.16; 'less,': 0.16; 'subject:Prime': 0.16; 'subject:generator': 0.16; 'thread,': 0.16; 'wrote:': 0.18; 'seems': 0.21; 'decide': 0.24; "i've": 0.25; 'possibly': 0.26; 'values': 0.27; 'gets': 0.27; 'van': 0.27; 'header:In-Reply-To:1': 0.27; 'am,': 0.29; 'quickly': 0.29; 'thus': 0.29; 'needed.': 0.30; 'message-id:@mail.gmail.com': 0.30; 'dramatic': 0.31; 'this.': 0.32; 'but': 0.35; 'received:google.com': 0.35; 'there': 0.35; 'indexed': 0.36; 'leads': 0.36; 'done': 0.36; 'similar': 0.36; 'list': 0.37; 'to:addr:python-list': 0.38; 'fact': 0.38; 'track': 0.38; 'to:addr:python.org': 0.39; 'around.': 0.60; 'then,': 0.60; "you've": 0.63; 'kind': 0.63; 'more': 0.64; '30,': 0.65; 'believe': 0.68; 'containing': 0.69; 'jul': 0.74; 'present.': 0.74; 'upper': 0.74; 'lack': 0.78; 'actually,': 0.84; 'avoids': 0.84; 'hanging': 0.84; 'remembering': 0.84; 'albert': 0.91; 'inefficient': 0.91; '2013': 0.98
DKIM-Signature	v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type; bh=94ivsj426/yZ8hhVugSLNJ84lDL8wUugHOqSOaGMNi0=; b=MsHky2XLeys7ogD1NDUoTc52QXZ4PRU5Uf+F3QnSdT+S9YsfkZjl+O0VK5lwWnrk68 6eii2eZ9+GMy17BLirJGNxgoSHiIZCa7HqD7X0b11RQmbDKB7GVX5UXbvbpb6emFkOWb 7vgNNffM3yHjTawZPB3hyttDH0OlT8YfOtYTMoeryOMhrk3qX26ZeDJgNOwIsznJN+ds kA5EgrE0jdKg3Jb0faZ23XVrVZm+llWrs9jzic5D9rdzGwlgQmNxVzZS+bsfs20Cg3Ms /4F94yZSAY9yFT497P3akU6kgook/ZTB2GAoKsOI7cyKxWTYvd8cSM01kfw1FId3pvDP dQsA==
X-Received	by 10.66.102.1 with SMTP id fk1mr2844577pab.90.1375205666841; Tue, 30 Jul 2013 10:34:26 -0700 (PDT)
MIME-Version	1.0
In-Reply-To	<51f79c4c$0$1672$e4fe514c@dreader35.news.xs4all.nl>
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	Tue, 30 Jul 2013 11:33:46 -0600
Subject	Re: Prime number generator
To	Python <python-list@python.org>
Content-Type	text/plain; charset=ISO-8859-1
X-Mailman-Approved-At	Wed, 31 Jul 2013 14:07:43 +0200
X-BeenThere	python-list@python.org
X-Mailman-Version	2.1.15
Precedence	list
List-Id	General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe	<http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive	<http://mail.python.org/pipermail/python-list/>
List-Post	<mailto:python-list@python.org>
List-Help	<mailto:python-list-request@python.org?subject=help>
List-Subscribe	<http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups	comp.lang.python
Message-ID	<mailman.15.1375272465.1251.python-list@python.org> (permalink)
Lines	25
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1375272465 news.xs4all.nl 15891 [2001:888:2000:d::a6]:49404
X-Complaints-To	abuse@xs4all.nl
Xref	csiph.com comp.lang.python:51645

Show key headers only | 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