Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #50377 > unrolled thread

Re: Prime number generator

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Prime number generator Ian Kelly <ian.g.kelly@gmail.com> - 2013-07-10 10:16 -0600

#50377 — Re: Prime number generator

On Wed, Jul 10, 2013 at 8:00 AM, Chris Angelico <rosuav@gmail.com> 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.

[toc] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web