Prime number generator in Python

The Sieve of Eratosthenes [en.wikipedia.org] 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

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


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

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.
 
This article has been posted on Oct 26, 2009 by Fred Cirera @ 09:44.

Leave a message

(Required)
(Required and not displayed)
(Optional)
obfuscated letters Enter the text shown in the image