A dumb question about a class

[Steven Bethard]

Steven Bethard wrote:
> 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.

Ok, I played around with it myself.  Here are the two implementations I 
tested::

     def iter_primes_recursive():
         # 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)


     def iter_primes_mapping():

         # mapping from composite number to first prime that revealed
         # that number as a composite
         composite_to_factor_map = {}

         # generate primes forever
         for i in itertools.count(2):

             # find a factor of the number
             factor = composite_to_factor_map.pop(i, None)

             # if no factor is found, the number is prime
             if factor is None:
                 yield i
                 composite_to_factor_map[i * i] = i

             # add the factor to the number until we find a new
             # composite number
             else:
                 composite = i + factor
                 while composite in composite_to_factor_map:
                     composite += factor
                 composite_to_factor_map[composite] = factor

And here are some timeit results::

$ python -m timeit -s "from script import iter_primes_recursive as 
iter_primes" "for i in iter_primes():" "    if i >= 100:"
"        break"
10000 loops, best of 3: 102 usec per loop

$ python -m timeit -s "from script import iter_primes_mapping as 
iter_primes" "for i in iter_primes():" "    if i >= 100:"
"        break"
10000 loops, best of 3: 75.2 usec per loop

$ python -m timeit -s "from script import iter_primes_recursive as 
iter_primes" "for i in iter_primes():" "    if i >= 10000:"
"        break"
10 loops, best of 3: 111 msec per loop

$ python -m timeit -s "from script import iter_primes_mapping as 
iter_primes" "for i in iter_primes():" "    if i >= 10000:"
"        break"
100 loops, best of 3: 8.4 msec per loop

So, somewhat unsurprisingly, the non-recursive version is much faster 
for larger primes. (Someone should check that both my implementations 
are right -- I only did a couple of spot checks on the output.)

STeVe