Это простой генератор pythonic

Является ли следующий код для генерации простых чисел pythonic?

def get_primes(n):
    primes=[False,False]+[True]*(n-1)
    next_p=(i for i,j in enumerate(primes) if j)
    while True:
        p=next(next_p)
        yield p
        primes[p*p::p]=[False]*((n-p*p)//p+1)

Обратите внимание, что следующий (next_p) в конечном итоге вызовет ошибку StopIteration, которая каким-то образом завершит функцию get_primes. Это плохо?

Также обратите внимание, что next_p - это генератор, который выполняет итерацию по простым числам, однако переменные меняются во время итерации. Это плохой стиль?

добавление следующего выражения if получает его менее 0,25 секунды для первого миллиона простых чисел:

if p*p<=n:
    primes[p*p::p]=[False]*((n-p*p)//p+1)

Ответ 1

Неплохо, что next(next_p) выдает ошибку StopIteration - то, что генератор всегда делает, когда заканчивается элемент!

Изменение длины списка при итерации по нему - плохая идея. Но нет ничего плохого в простом изменении содержимого. В целом, я думаю, что это довольно элегантная, если базовая, сильная.

Одно небольшое наблюдение: когда вы "вычеркиваете" кратные простые числа, вы обнаружите, что если вы немного подумаете об этом, вам не нужно начинать с p * 2. Вы можете перейти к p ** 2.

Ответ 2

В StopIteration нет ничего плохого, действительно, это ожидаемое поведение генераторов.

Я бы сказал, что эта реализация более питонична (не обязательно более эффективна):

def get_primes(n):
  """Generates prime numbers < n"""
  return (x for x in xrange(2,n) if all(x % i for i in xrange(2,x)))

Pythonic для меня означает четкость, краткость, удобочитаемость и использование сильных сторон языка. Хотя я вижу, что ваша реализация - это какое-то сито, я знаю только это из предыдущего опыта с такими алгоритмами. Выполнение выше, я могу читать непосредственно как прямое испытание делимости.

Примечание: есть незначительная разница в интерфейсе, ваша реализация будет давать простые числа <= n, тогда как моя реализация будет давать простые числа < п. Очевидно, что это можно легко и тривиально изменить (просто измените n на n + 1 в теле функции), но я чувствую, что более pythonic более эффективно генерировать простые числа, но не включать n, чтобы быть более согласованным с тем, скажем, range() встроенные работы.

РЕДАКТИРОВАТЬ: ТОЛЬКО ДЛЯ FUN

Ниже представлена наименее пифоническая реализация и, вероятно, довольно неэффективная:)

def get_primes(n):
  import re
  return (x for x in xrange(2,n) if re.match(r'^1?$|^(11+?)\1+$', '1' * x) is None)

Я называю это наименее pythonic, потому что вы будете царапать голову в течение нескольких дней, чтобы выяснить, как это работает, если вы еще не видели этот трюк раньше!

Ответ 3

Вот еще несколько несколько pythonic решение, мотивированное @wim, однако вы можете видеть, что он немного медленнее первого метода.

def get_primes2(n):
    primes=[]
    for i in range(2,n+1):
        small_primes=(p for p in primes if p*p<=i)
        if all(i%p for p in small_primes):
            yield i
            primes.append(i)

import timeit
print(timeit.timeit("list(get_primes(10**5))",number=5,setup="from __main__ import get_primes")/5.0)
"0.0350940692182945"
print(timeit.timeit("list(get_primes2(10**5))",number=5,setup="from __main__ import get_primes2")/5.0)
"8.226938898658908"