Ответ 1

Сито Эратосфена в двух строках.

primes = set(range(2,1000000))
for n in [2]+range(3,1000000/2,2): primes -= set(range(2*n,1000000,n))

Изменить: я понял, что выше это не истинное сито Эратосфена, потому что оно фильтрует множество нечетных чисел, а не множество простых чисел, делая его излишне медленным. Я исправил это в следующей версии, а также включил ряд общих оптимизаций, как указано в комментариях.

primes = set([2] + range(3, 1000000, 2))
for n in range(3, int(1000000**0.5)+1, 2): primes -= set(range(n*n,1000000,2*n) if n in primes else [])

Первая версия все еще короче и генерирует правильный результат, даже если это занимает больше времени.

Ответ 2

Так как можно просто вырезать и вставить первые миллионы простых чисел из сети:

map(int,open('primes.txt'))

Это несколько похоже на вопрос, который я задал вчера, где wim предоставил довольно короткий ответ:

это пирамида генератора простых чисел

Ответ 3

Подобно вышесказанному, но не так дерзко, как Роберт Кинг отвечает:

from itertools import ifilter, imap
def primes(max=3000):
    r = set(); [r.add(n) for n in ifilter(lambda c: all(imap(c.__mod__, r)), xrange(2, max+1))]; return sorted(r)

Ответ 4

Это использует больше символов, но читается:

def primes_to(n):
    cands = set(xrange(2, n))
    for i in xrange(2, int(n ** 0.5) + 1):
        for ix in xrange(i ** 2, n, i):
            cands.discard(ix)
    return list(cands) 

ИЗМЕНИТЬ

Новый способ, аналогичный приведенному выше, но с менее пропущенными попытками в discard:

def primes_to(n):
    cands = set(xrange(3, n, 2))
    for i in xrange(3, int(n ** 0.5) + 1, 2):
        for ix in xrange(i ** 2, n, i * 2):
            cands.discard(ix)
    return [2] + list(cands)