The Sieve of Eratosthenes is a fast and simple algorithm to generate all the primes in a range.
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 except IndexError: break seq = filter(p.__rmod__, seq) primes.append(p) return primes
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.