A dumb question about a class
Steven Bethard
steven.bethard at gmail.com
Mon Aug 13 04:24:53 CEST 2007
Dustan wrote:
> 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?
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
More information about the Python-list
mailing list