# A dumb question about a class

Steven Bethard steven.bethard at gmail.com
Mon Aug 13 04:56:16 CEST 2007

```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

```