Dustan wrote: > On Aug 12, 7:35 pm, Dustan <[EMAIL PROTECTED]> wrote: >> On Aug 12, 5:09 pm, Steven Bethard <[EMAIL PROTECTED]> 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?
I don't have the answer off hand, but if anyone wants to report some timeit results or memory consumption here, I'd be interested. STeVe -- http://mail.python.org/mailman/listinfo/python-list
