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>
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

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)).