Steven Bethard wrote:

Dustan wrote:
>On Aug 12, 7:35 pm, Dustan <DustanGro...@gmail.comwrote:
>>On Aug 12, 5:09 pm, Steven Bethard <steven.beth...@gmail.comwrote:

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