Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!feeder.news-service.com!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!194.109.133.85.MISMATCH!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!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: OK 0.006
X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; 'bug': 0.02; 'wed,': 0.03; 'modified': 0.05; 'integers': 0.09; 'def': 0.12; 'am,': 0.14; 'wrote:': 0.14; 'consecutive': 0.16; 'efficiently.': 0.16; 'happens.': 0.16; 'integers.': 0.16; '\xa0this': 0.16; '\xa0while': 0.16; 'cc:addr:python-list': 0.17; 'cheers,': 0.19; 'header:In-Reply-To:1': 0.21; 'appears': 0.21; 'seems': 0.21; 'cc:2**0': 0.22; 'cc:no real name:2**0': 0.23; 'along.': 0.23; 'statement,': 0.23; 'unlikely': 0.23; '\xa0if': 0.23; 'received:209.85.161.46': 0.23; 'received:mail- fx0-f46.google.com': 0.23; "doesn't": 0.25; 'received:209.85.161': 0.26; 'fixed': 0.27; 'message-id:@mail.gmail.com': 0.28; 'version': 0.29; 'subject:How': 0.30; 'cc:addr:python.org': 0.30; 'array': 0.30; "can't": 0.32; 'does': 0.33; 'rather': 0.34; 'there': 0.35; 'certain': 0.36; 'uses': 0.36; 'table': 0.37; 'received:google.com': 0.37; 'received:209.85': 0.37; 'despite': 0.37; 'case': 0.37; 'two': 0.37; 'url:python': 0.38; 'could': 0.38; 'subject:can': 0.38; 'url:org': 0.38; 'but': 0.38; 'subject:: ': 0.38; 'subject: (': 0.39; 'perhaps': 0.39; 'received:209': 0.39; 'add': 0.39; 'happen': 0.60; 'generate': 0.60; 'further': 0.65; 'cause': 0.67; 'square': 0.67; 'traditional': 0.68; 'prime': 0.73; 'melissa': 0.84; 'subject:over': 0.84; 'yielded': 0.84
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-type:content-transfer-encoding; bh=rCJHIAy8vhMDoQwICi27cHot/o6eZWnJVlJBwEvmgCY=; b=s/kRIxQyvvFII4A1+e4cOj5EtipiwclhoDsS2CGEwq9a7aEkMKpoPzz+IhcL7cs61k qJNVkMbcF8Iy2Vv2YUKJfqVl4clJGOFu2jTsk84fntuw7uM+BtkcbjGl/uMxjqm/Mc77 0BT4pom7RoD4JOGqH+IatmIZbAxP/71hwhk+Q=
DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type:content-transfer-encoding; b=JNKU5RaHDMB7hgtZRHbqFbygHoGJ+EFYq4Q2VjHlx5fBtwjN/uhTXBPXM5ToAi1H3X FFLfUe21W8VXmpPTSRbYr9K4oNnYbTP4wsSvzn8BnkEvQeh0UqOofVfFJS15drBeN6r4 1s5eHnF7eJUQC486PhtKdTijm/yMoWc697I54=
MIME-Version: 1.0
In-Reply-To: <4e01d983$0$29977$c3e8da3$5496439d@news.astraweb.com>
References: <f97b3159-318a-41e2-9f28-339fa4a81d79@k6g2000yqc.googlegroups.com> <its0ar02sia@news2.newsguy.com> <4e01d983$0$29977$c3e8da3$5496439d@news.astraweb.com>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Wed, 22 Jun 2011 09:52:40 -0600
Subject: Re: How can I speed up a script that iterates over a large range (600 billion)?
To: Anny Mous <b1540457@tyldd.com>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Cc: python-list@python.org
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.12
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.285.1308757993.1164.python-list@python.org>
Lines: 50
NNTP-Posting-Host: 82.94.164.166
X-Trace: 1308757994 news.xs4all.nl 49181 [::ffff:82.94.164.166]:34467
X-Complaints-To: abuse@xs4all.nl
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:8219

On Wed, Jun 22, 2011 at 6:01 AM, Anny Mous <b1540457@tyldd.com> wrote:
> def sieve():
> =A0 =A0"""Yield prime integers efficiently.
>
> =A0 =A0This uses the Sieve of Eratosthenes, modified to generate the prim=
es
> =A0 =A0lazily rather than the traditional version which operates on a fix=
ed
> =A0 =A0size array of integers.
> =A0 =A0"""
> =A0 =A0# This implementation based on a version by Melissa E. O'Neill,
> =A0 =A0# as reported by Gerald Britton:
> =A0 =A0# http://mail.python.org/pipermail/python-list/2009-January/118852=
9.html
> =A0 =A0innersieve =3D sieve()
> =A0 =A0prevsq =3D 1
> =A0 =A0table =A0=3D {}
> =A0 =A0i =3D 2
> =A0 =A0while True:
> =A0 =A0 =A0 =A0if i in table:
> =A0 =A0 =A0 =A0 =A0 =A0prime =3D table[i]
> =A0 =A0 =A0 =A0 =A0 =A0del table[i]
> =A0 =A0 =A0 =A0 =A0 =A0nxt =3D i + prime
> =A0 =A0 =A0 =A0 =A0 =A0while nxt in table:
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0nxt +=3D prime
> =A0 =A0 =A0 =A0 =A0 =A0table[nxt] =3D prime
> =A0 =A0 =A0 =A0else:
> =A0 =A0 =A0 =A0 =A0 =A0yield i
> =A0 =A0 =A0 =A0 =A0 =A0if i > prevsq:
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0j =3D next(innersieve)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0prevsq =3D j**2
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0table[prevsq] =3D j
> =A0 =A0 =A0 =A0i +=3D 1

This appears to have a small bug in it, but perhaps it doesn't matter.
 At the "yield i" statement, it is possible that i > prevsq.  It could
be that i =3D=3D next(innersieve)**2, in which case i is yielded as prime
despite being composite.  This would then cause additional errors
further along.

The only way this could happen would be if there were two consecutive
primes such that all the numbers between their squares are composite,
thereby failing to add the next prime to the table until after its
square has been reached.  This seems a rather unlikely scenario, but I
can't say for certain that it never happens.

The Haskell version does not contain this flaw, as far as I can tell.

Cheers,
Ian