A dumb question about a class

Dustan DustanGroups at gmail.com
Mon Aug 13 02:57:28 CEST 2007


On Aug 12, 7:35 pm, Dustan <DustanGro... at gmail.com> wrote:
> On Aug 12, 5:09 pm, Steven Bethard <steven.beth... at gmail.com> wrote:
>
> >      def iter_primes():
> >          # an iterator of all numbers between 2 and +infinity
> >          numbers = itertools.count(2)
>
> >          # generate primes forever
> >          while True:
>
> >              # get the first number from the iterator (always a prime)
> >              prime = numbers.next()
> >              yield prime
>
> >              # remove all numbers from the (infinite) iterator that are
> >              # divisible by the prime we just generated
> >              numbers = itertools.ifilter(prime.__rmod__, numbers)
>
> This is kind of OT (from the thread), but in this iter_primes
> function, numbers is becoming an ifilter of an ifilter of an ifilter
> of an ifilter of an ifilter of an ifilter of... Is that really at all
> efficient for larger numbers (millions or billions, or even bigger)?

To word my question better:

How does this algorithm compare and contrast to maintaining a
dictionary or set and iterating through those structures to find out
if a number is divisible? All of those algorithms I've described are
O(n^2), if I'm not mistaken, but as far as memory-efficiency and the
likes, how do they compare/contrast?




More information about the Python-list mailing list