The Sieve of Eratosthenes is a fast and simple algorithm to generate all the primes in a range.

Lists

In our first example we use lists. In each loop we take the first number of the sequence and use the filter to remove every multiple of that number. When the sequence is empty we stop the loop and return the list of prime numbers we have found.

def eratos(upperBound):
    primes = []
    seq = range(2, upperBound + 1)
    while True:
        try:
            p = seq[0]
        except IndexError:
            break
        seq = filter(p.__rmod__, seq)
        primes.append(p)
    return primes

Using Iterators

The following example uses the same algorithm, but with Python “iterators” instead of lists. The main advantage with this method is that we don't have to pre-allocate any sequence of numbers in memory.

from itertools import count, ifilter
def i_eratos():
    seq = count(2)
    while True:
        p = seq.next()
        seq = ifilter(p.__rmod__, seq)
        yield p

Using this method I managed to generate more that 131.000 prime numbers, before Python crashed with a Segmentation fault message.