Sieve of Eratosthenes

Here is a simple implementation of the Sieve of Eratosthenes in Python.

from math import sqrt
def sieve(N):
    """Sieve of Eratosthenes.  Returns primes less than N

    http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    """
    # Set up the array.  2 is the first prime, not 1.
    ar = range(N)
    ar[1] = 0

    limit = 1 + int(sqrt( N))
    for d in xrange(2,limit):
        if ar[d]:
            # d is prime!  mark off the multiples of d.
            # note that we can start with d*d instead of 2*d.
            for j in xrange(d*d,N,d):
                ar[j] = 0
    return [x for x in ar if x]

There are several optimizations that people tend to do when they write this algorithm. But, this gets us most of the way. I keep rewriting this function for Project Euler problems, but I should really keep a library of the functions I use, or better yet, use Sage.