A dumb question about a class

[Steven Bethard]

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