Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <rosuav@gmail.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.013
X-Spam-Evidence: '*H*': 0.97; '*S*': 0.00; 'algorithm': 0.04; 'bootstrap': 0.07; 'smallest': 0.07; 'repeated': 0.09; 'sake': 0.09; 'subject:number': 0.09; 'def': 0.12; '2*i': 0.16; 'dict': 0.16; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'lookups': 0.16; 'pypi.': 0.16; 'simple.': 0.16; 'subject:Prime': 0.16; 'subject:generator': 0.16; 'there...': 0.16; 'think.': 0.16; 'true:': 0.16; 'winner.': 0.16; 'wrote:': 0.18; '(but': 0.19; 'thu,': 0.19; 'import': 0.22; 'library,': 0.24; 'replace': 0.24; "i've": 0.25; 'least': 0.26; 'asking': 0.27; 'header:In-Reply- To:1': 0.27; 'am,': 0.29; 'message-id:@mail.gmail.com': 0.30; 'code': 0.31; 'constant': 0.31; 'though.': 0.31; 'guess': 0.33; '"the': 0.34; "i'd": 0.34; 'but': 0.35; 'received:google.com': 0.35; 'there': 0.35; 'version': 0.36; 'yield': 0.36; 'next': 0.36; "i'll": 0.36; 'effort': 0.37; 'so,': 0.37; 'list.': 0.37; 'minimum': 0.38; 'star': 0.38; 'to:addr:python-list': 0.38; 'little': 0.38; 'anything': 0.39; 'does': 0.39; 'though,': 0.39; 'to:addr:python.org': 0.39; 'skip:p 20': 0.39; 'is.': 0.60; 'course': 0.61; 'name': 0.63; 'kind': 0.63; 'map': 0.64; 'series': 0.66; 'jul': 0.74; 'now:': 0.74; 'prime': 0.74; '"one': 0.84; 'algorithm,': 0.84; 'have?': 0.84; 'presumably': 0.84; 'composite': 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:date:message-id:subject:from:to :content-type; bh=JkbDhmUHBHvZfTh170ec5H/A1VIQJl57qHFjXhkRVhw=; b=wA8W8U6LDcDZWSlBOx6RVqj5VTmRyThY0oHiDvURpDTIodWGJJPx2+odjNAiadfQdb EEOtuIROJPX+lomEYISQWvWrqd0lh5dqzVmdVhDb46uyd8pYpNyh3lDr7XWOudHgOFId NdEBQHHOxpzbatfQ2EWzKFYAYsC1Ses3w3M3LjK9k3ElIrYMCLQDY2ytxAvbCccN02/O WdTL+NKyaMqNKNH6PWvE1nSv6IrbwytHnX0Y64tle3XOVKt6c+ns2BkqkMsLxfsO2Njl AMtSqAQpoeHxBjl6vljY9sO9wZJ4LKexIbF2/2Xd9xsBVSB7vBgfQaCGhAMLoVnxsr64 Wd/A==
MIME-Version: 1.0
X-Received: by 10.220.169.146 with SMTP id z18mr19455591vcy.80.1373472194245; Wed, 10 Jul 2013 09:03:14 -0700 (PDT)
In-Reply-To: <CAN1F8qWSOBw5Z1+obbZt1Rwg+R393KEUPRCF=W42hR+QLu8JhQ@mail.gmail.com>
References: <CAPTjJmq_7+rtNV22cxpLXQ+G1XfCyJvKckN+2B3PjfVEEs-5Qw@mail.gmail.com> <CAN1F8qWSOBw5Z1+obbZt1Rwg+R393KEUPRCF=W42hR+QLu8JhQ@mail.gmail.com>
Date: Thu, 11 Jul 2013 02:03:14 +1000
Subject: Re: Prime number generator
From: Chris Angelico <rosuav@gmail.com>
To: python-list@python.org
Content-Type: text/plain; charset=ISO-8859-1
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.4531.1373472203.3114.python-list@python.org>
Lines: 65
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1373472203 news.xs4all.nl 15969 [2001:888:2000:d::a6]:34727
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:50372

On Thu, Jul 11, 2013 at 1:43 AM, Joshua Landau <joshua@landau.ws> wrote:
>> So, a few questions. Firstly, is there...
> Of course there is.
>
>> Secondly, can the...
> Of course it can.
>
>> Thirdly, is there...
> Of course there is. I have no clue what, though.

Heh, I guess I was asking for that kind of response :)

> The trick
> is to avoid that repeated effort of finding the minimum in the dict by
> just keeping a sorted list.
>
> I've mocked that up just now:
>
> # Faster code #
> from blist import sortedlist

Hmm, blist isn't part of the standard library, so I'd have to hunt
that down. Presumably it's on PyPI.

>> What name would this algorithm have?
> I'll call it "the flamingo".

Guess that's as good a name as any!

> def generate_primes():
>         """Generate an infinite series of prime numbers."""
>         i = 2
>         yield 2
>
>         primes = {2:2} # Map a prime number to its next composite (but
> bootstrap with 2:2)
>         while True:
>                 prm = min(primes, key=primes.__getitem__)
>                 smallest = primes[prm]
>
>                 primes[prm] += prm
>
>                 for prm in range(i, smallest):
>                         yield prm
>                         primes[i] = 2*i
>
>                 i = smallest + 1
>
> gen=generate_primes()
> for i in range(30):
>         print(next(gen),end="\t") # Star Trek?
> print()

And once again, a version that's slower than the original. This one
does at least have the advantage of readability, though, and it's only
a little slower, so I'd say this is the current winner. I would still
replace 2*i with i+i for the sake of boasting "no multiplication",
though :)

In terms of the "one pass" criterion I put on the find-smallest
algorithm, I had been seeking to avoid anything that involved constant
lookups into primes[]. But this solution does look very clean and
simple. I think.

ChrisA