это генератор простых чисел питона - PullRequest
Новая
       11

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

5 голосов
/ 15 февраля 2012

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

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 (next_p) в конечном итоге выдаст ошибку StopIteration, которая каким-то образом завершает функцию get_primes.Это плохо?

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

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

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

Ответы [ 3 ]

3 голосов
/ 15 февраля 2012

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

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

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

2 голосов
/ 15 февраля 2012

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

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

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

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)

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

0 голосов
/ 15 февраля 2012

Вот еще одно несколько питоническое решение, мотивированное @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"
...