This got me through many of the first 100 problems on Project Euler:

    n = 1000000 # must be even
    sieve = [True] * (n/2)
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i/2]: sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
    …
    # x is prime if x%2 and sieve[x/2]