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

Question

Является ли следующий код для генерации простых чисел 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 - это генератор, который выполняет итерацию по простым числам, однако переменные меняются во время итерации. Это плохой стиль?

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

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

Answer 1

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

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

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

Answer 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 + 1 в теле функции), но я чувствую, что более pythonic более эффективно генерировать простые числа, но не включать n, чтобы быть более согласованным с тем, скажем , range() сборник работ.

---

EDIT: JUST FOR 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) 

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

Answer 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"