Title: Prime sieve generators
Submitter: Aaron Gallagher (other recipes)
Last Updated: 2008/04/25
Version no: 1.3
Category: Algorithms

Description:

Two simple generators for generating prime numbers using a prime sieve. gen_sieve(n) will produce all prime numbers
isprime is an example of how one could use gen_sieve: a quick function for testing primality by attempting modulo division with each potential prime factor of a number.

Source: Text Source

import math

def gen_sieve(ceiling=None):
    if ceiling is not None:
        if ceiling % 2 == 0:
            ceiling -= 1
        highest_prime = math.ceil(math.sqrt(ceiling))
    last_val = 1
    found_primes = []
    yield 2
    while ceiling is None or ceiling > last_val:
        current_val = None
        while current_val is None:
            current_val = last_val = last_val + 2
            for prime, square in found_primes:
                if current_val < square: 
                    break
                if current_val % prime == 0:
                    current_val = None
                    break
        yield current_val
        if ceiling is None or highest_prime > last_val:
            found_primes.append((current_val, current_val ** 2))

def isprime(n):
    for fac in gen_sieve(int(math.ceil(math.sqrt(n)))):
        if n % fac == 0 and n != fac:
            return fac
    return 0

Discussion:

This is the fastest prime sieve I could come up with in python. There might be a way to reduce the memory footprint.