Stuff

from math import sqrt

def primes(n):
    """ Use sieve of Eratosthenes to find all primes <= n """
    R = {x for x in range(2,n+1)} # search space
    k = 2 # first prime
    while True:
        if k in R:
            i = k # minor optimization: k^2 is first unmarked multiple
            while k*i <= n:
                R.discard(k*i)
                i += 1
        k += 1
        if k >= sqrt(n): return R

# from http://macdevcenter.com/pub/a/python/excerpt/pythonckbk_chap1/index1.html?page=2
import itertools
def eratosthenes():
    '''Yields the sequence of prime numbers via the Sieve of Eratosthenes.'''
    D = {  }  # map each composite integer to its first-found prime factor
    for q in itertools.count(2):     # q gets 2, 3, 4, 5, ... ad infinitum
        p = D.pop(q, None)
        if p is None:
            # q not a key in D, so q is prime, therefore, yield it
            yield q
            # mark q squared as not-prime (with q as first-found prime factor)
            D[q*q] = q
        else:
            # let x <- smallest (N*p)+q which wasn't yet known to be composite
            # we just learned x is composite, with p first-found prime factor,
            # since p is the first-found prime factor of q -- find and mark it
            x = p + q
            while x in D:
                x += p
            D[x] = p