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

Question

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

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

Answer 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 [])

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

Answer 2

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

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

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

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

Answer 3

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

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)

Answer 4

Как и выше, но не так дерзко, как ответ Роберта Кинга:

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)