Самый быстрый в пространстве-пространстве для нахождения простых чисел с питоном

Возможно, это глупый вопрос, но мне было интересно, можно ли предоставить самый короткий источник для нахождения простых чисел с Python. Мне также интересно, как найти простые числа, используя функции map() или filter(). Спасибо (:

EDIT: Когда я говорю "Самый быстрый/короткий", я имею в виду способ с меньшим количеством символов/слов. Во всяком случае, не рассматривайте соревнование: я задавался вопросом, возможен ли один источник с одной строкой, без удаления отступа, всегда используемого для циклов. РЕДАКТИРОВАТЬ 2: Проблема не была задумана для огромных чисел. Я думаю, что мы можем остаться под миллионом (диапазон (21000000) РЕДАКТИРОВАТЬ 3: Самый короткий, но все же элегантный. Как я сказал в первом EDIT, вам не нужно уменьшать имена переменных на отдельные буквы. Мне просто нужна одна линия, элегантный источник. Спасибо!

Ответ 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)