To najlepszy algorytm, jaki mogłem wymyślić.

def get_primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return primes

>>> timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import   get_primes').timeit(1)
1.1499958793645562

Czy można to zrobić jeszcze szybciej?

Ten kod ma wadę: Sincenumbers jest nieuporządkowanym zestawem, nie ma takiej gwarancjinumbers.pop() usunie najniższy numer z zestawu. Niemniej jednak działa (przynajmniej dla mnie) dla niektórych liczb wejściowych:

>>> sum(get_primes(2000000))
142913828922L
#That's the correct sum of all numbers below 2 million
>>> 529 in get_primes(1000)
False
>>> 529 in get_primes(530)
True