Some prime generation algorithms. (Python recipe) by Thomas Lehmann

ActiveState Code (http://code.activestate.com/recipes/577329/)

"""
 Topic: prime algorithms.
 Here is an example output of this script:

 Totally free. No warranty.

Python 3.1.2 (r312:79149, Mar 21 2010, 00:41:52) [MSC v.1500 32 bit (Intel)]

 [calc_slower]
 seeking primes between (0..100000) ...
 ...profiling of 'create_primes_1': tooks 6.974707 seconds
 ...profiling of 'create_primes_2': tooks 0.195253 seconds
 ...profiling of 'create_primes_3': tooks 0.090312 seconds
 ...profiling of 'create_primes_4': tooks 0.062241 seconds
 ...profiling of 'create_primes_5': tooks 0.046717 seconds
 ...profiling of 'create_primes_6': tooks 0.024859 seconds
 done - 9592 primes found.

 [calc_medium]
 seeking primes between (0..1000000) ...
 ...profiling of 'create_primes_2': tooks 4.662721 seconds
 ...profiling of 'create_primes_3': tooks 1.133545 seconds
 done - 78498 primes found.

 [calc_faster]
 seeking primes between (0..10000000) ...
 ...profiling of 'create_primes_3': tooks 13.872371 seconds
 ...profiling of 'create_primes_4': tooks 7.766646 seconds
 ...profiling of 'create_primes_5': tooks 6.069688 seconds
 done - 664579 primes found.

Are there no better solutions? ... smile ... Of course there are many!
But unfortunately some of them require a much better understanding in
math and I'm afraid (for myself) that some explanations are not simple
enough so I can present them here.
"""
import sys
import time
import math

def profile(function):
    """ intended to be used as decorator for a function or a method to check
        the execution time """

    def decorate(args):
        """ concrete decorator measuring the execution time of
            given function or method """
        start = time.clock()
        result = function(args)
        print("...profiling of '%s': tooks %f seconds" \
              % (function.__name__, time.clock()-start))
        #print("  -> %s" % (function.__doc__))
        return result
    return decorate


def is_prime(val):
    """ simple check for a prime value.
        Note: as a function called several time it is expensive. """
    if val <= 1:
        return False
    if val == 2:
        return True
    if val % 2 == 0:
        return False

    for divisor in range(3, int(math.sqrt(val))+1, 2):
        if val % divisor == 0:
            return False

    return True


@profile
def create_primes_1(max_n):
    """ creating primes up to a maximum value. The even numbers are not
        touched. The primes itself are used to check for possible division. """
    primes = []
    for val in range(3, max_n+1, 2):
        found = False
        for divisor in primes:
            if val % divisor == 0:
                found = True
                break

        if not found:
            primes.append(val)
    return [2] + primes


@profile
def create_primes_2(max_n):
    """ creating primes up to a max. value calling 'is_prime' for each value. """
    primes = [2]+[val for val in range(3, max_n+1, 2) if is_prime(val)]
    return primes

@profile
def create_primes_3(max_n):
    """ using sieve of sundaram:
        http://en.wikipedia.org/wiki/Sieve_of_Sundaram
        The description was really understandable   """
    limit    = max_n + 1
    sieve    = [True] * (limit)
    sieve[1] = False

    for i in range(1, limit//2):
        f = 2 * i + 1
        for j in range(i, limit//2):
            k = i + j * f
            if k <= max_n:
                sieve[k] = False
            else:
                break

    return [2,3]+[2*k+1 for k in range(1, int(max_n/2)) if sieve[k]]

@profile
def create_primes_4(max_n):
    """ creating primes up to a maximum value using a sieve algorithm. All
        multiples of a prime are flagged as 'no prime'. In addition there
        is an optimization by ignoring values flagged as none prime when
        proceeding to next value."""
    sieve = [True] * (max_n+1) # default: all are primes
    sieve[0] = False           # init:    0 is not a prime
    sieve[1] = False           # init:    1 is not a prime

    val = 2
    while val <= max_n:
        factor = val
        # strike out values not being a prime
        noprime = val * factor
        while noprime <= max_n:
            sieve[noprime] = False
            factor += 1
            noprime = val * factor
        # next value
        val += 1
        while val <= max_n and sieve[val] == False:
            val += 1

    return [n for n in range(max_n) if sieve[n] == True]


@profile
def create_primes_5(max_n):
    """ creating primes up to a maximum value using a sieve algorithm. All
        multiples of a prime are flagged as 'no prime'. In addition there
        is an optimization by ignoring values flagged as none prime when
        proceeding to next value."""
    sieve  = [False, True] * (int(max_n / 2))
    sieve += [True]

    if not max_n % 2 == 0:
        sieve += [False]


    sieve[1] = False
    sieve[2] = True
    primes   = [2]

    val = 3
    while val <= max_n:
        # now we have one prime
        primes.append(val)
        # strike out values not being a prime
        noprime = val + val
        while noprime <= max_n:
            sieve[noprime] = False
            noprime += val
        # next value
        val += 1
        while val <= max_n and sieve[val] == False:
            val += 1

    return primes


@profile
def create_primes_6(max_n):
    """ creating primes up to a maximum value using a sieve algorithm. All
        multiples of a prime are flagged as 'no prime'. In addition there
        is an optimization by ignoring values flagged as none prime when
        proceeding to next value."""
    sieve  = [False, True] * (max_n // 2)
    sieve += [False]

    sieve[1] = False
    sieve[2] = True
    primes   = [2]

    val = 3
    while val <= max_n:
        # now we have one prime
        primes.append(val)
        # strike out values not being a prime
        offset  = val * 2
        noprime = val + offset
        while noprime <= max_n:
            sieve[noprime] = False
            noprime += offset
        # next value
        val += 2
        while val <= max_n:
            if not sieve[val]:
                val += 2
            else:
                break

    return primes


def calc_slower(max_n):
    """ scenario I - displaying relation and validate results """
    print("\n[%s]" % (sys._getframe().f_code.co_name))
    print("seeking primes between (0..%d) ..." % (max_n))
    primes1 = create_primes_1(max_n)
    primes2 = create_primes_2(max_n)
    primes3 = create_primes_3(max_n)
    primes4 = create_primes_4(max_n)
    primes5 = create_primes_5(max_n)
    primes6 = create_primes_6(max_n)

    assert primes1 == primes2 == primes3 == primes4 == primes5 == primes6
    print("done - %d primes found." % (len(primes4)))


def calc_medium(max_n):
    """ scenario II - testing 'is_prime' alone """
    print("\n[%s]" % (sys._getframe().f_code.co_name))
    print("seeking primes between (0..%d) ..." % (max_n))
    primes2 = create_primes_2(max_n)
    primes3 = create_primes_3(max_n)
    print("done - %d primes found." % (len(primes2)))


def calc_faster(max_n):
    """ scenario III - testing sieve alone """
    print("\n[%s]" % (sys._getframe().f_code.co_name))
    print("seeking primes between (0..%d) ..." % (max_n))
    primes3 = create_primes_3(max_n)
    primes4 = create_primes_4(max_n)
    primes5 = create_primes_5(max_n)
    print("done - %d primes found." % (len(primes4)))

if __name__ == "__main__":
    print("Python %s" % (sys.version))
    max_n = 100000
    calc_slower(max_n      )
    calc_medium(max_n *  10)
    calc_faster(max_n * 100)