Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!eu.feeder.erje.net!xlned.com!feeder7.xlned.com!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.066 X-Spam-Evidence: '*H*': 0.87; '*S*': 0.00; '21,': 0.07; '22,': 0.09; 'noted,': 0.09; 'subject:number': 0.09; 'dictionary.': 0.16; 'dig': 0.16; 'generator.': 0.16; 'heap': 0.16; 'mapped': 0.16; 'subject:Prime': 0.16; 'subject:generator': 0.16; '{2:': 0.16; 'wrote:': 0.18; 'wed,': 0.18; 'later': 0.20; 'instance,': 0.24; 'header:In-Reply-To:1': 0.27; 'chris': 0.29; 'am,': 0.29; 'message-id:@mail.gmail.com': 0.30; '(although': 0.31; '13,': 0.31; 'lists': 0.32; 'probably': 0.32; 'checking': 0.33; 'could': 0.34; 'something': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'next': 0.36; "i'll": 0.36; 'similar': 0.36; 'searching': 0.37; 'mapping': 0.38; 'somebody': 0.38; 'to:addr:python-list': 0.38; 'track': 0.38; 'rather': 0.38; 'structure': 0.39; 'to:addr:python.org': 0.39; 'first': 0.61; 'map': 0.64; 'more': 0.64; '20,': 0.68; 'jul': 0.74; 'prime': 0.74; '11:': 0.84; '13:': 0.84; 'different.': 0.84; 'min': 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:from:date:message-id:subject:to :content-type; bh=CnCOQZ0XXCnmqknkxmHi2T/Pijq8EJjEnbJa0CIEyRk=; b=DrwrcAa84S97wnd1cOrGsz19aVSSklBP86IcHdsH4mR8yQ1p6ryf/p4OoV9zq6T1XH 1ApVmtiAzLwxfwqFewDt/zA4AtQg/viyMuuMYFlRrWaUB6BZtRPcEj/Bjx6Tehgufrxu YS5mNRnBDxOcv7OzRShd9lWrwcZAHqr1esToCtIWkOgUoWh/vIHEMbR4UaqazLMa1Exb 8YCQyDJovfWhli2zQUMfu9BW6m1KnDW88g6Kg1LZor/lTknMkMjYPDov6jKSonW38/3t UCY7P7fQaFgv5k9cpxe7FzphyyJ+d/ZHULttd+bCn8DTKrC/cvIceU4zbEI2iGfDyhzN YzXw== X-Received: by 10.66.178.174 with SMTP id cz14mr34009699pac.136.1373473032246; Wed, 10 Jul 2013 09:17:12 -0700 (PDT) MIME-Version: 1.0 In-Reply-To: References: From: Ian Kelly Date: Wed, 10 Jul 2013 10:16:32 -0600 Subject: Re: Prime number generator To: Python 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 19 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1373473041 news.xs4all.nl 15887 [2001:888:2000:d::a6]:51615 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:50377 On Wed, Jul 10, 2013 at 8:00 AM, Chris Angelico wrote: > And now for something completely different. > > I knocked together a prime number generator, just for the fun of it, > that works like a Sieve of Eratosthenes but unbounded. It keeps track > of all known primes and the "next composite" that it will produce - > for instance, after yielding 13, the prime map will be {2: 20, 3: 18, > 5: 20, 7: 21, 11: 22, 13: 26}, each one mapped to the first multiple > greater than 13. Cool! I have a similar generator, and instead of mapping primes to next composites, it maps next composites to lists of primes. It works using increment-by-2 and checking the dictionary rather than searching for the min of the dictionary. You could though adapt that data structure and just use min(prime) to find the next composite (although as somebody else noted, a heap would probably be more efficient). The other interesting thing about my sieve is that it's a recursive generator. I'll dig it up later and share it.