是這個素數發生器pythonic

下面是用於生成素數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（next_p）最終會拋出一個StopIteration錯誤，該錯誤以某種方式結束函數get_primes。那不好嗎？

另請注意，next_p是一個在素數上進行迭代的生成器，但素數在迭代過程中會發生變化。那是不好的風格？

加入下面的if語句得到它控制在0.25秒的第一百萬質數：

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

來源

2012-02-15 robert king

可以節省一個行，如果你想使用'素數=假，假] + [真] *（N-1）'，也增加了複雜性，您可以優化使用半篩子，跳過偶數。看到http://stackoverflow.com/a/3035188/464543 – ChessMaster 2012-02-15 03:59:38

謝謝@ ChessMaster – 2012-02-15 04:06:37

測試你的代碼爲0,1,2,3沒有行'如果p * p <= n：'...在我的機器中行不需要 – ChessMaster 2012-02-15 04:20:26

這是不差那next(next_p)拋出一個StopIteration錯誤 - 那就是始終發電機並當它運行了項目！

迭代列表時更改列表的長度是一個壞主意。但簡單地改變內容並沒有錯。總的來說，我認爲這是一個相當優雅的，如果基本的，有活力的。

一個小小的觀察：當你「剔除」多個質數時，如果你仔細想一下，你會發現你不必以p * 2開頭。您可以跳到p ** 2。

來源

2012-02-15 03:33:30 senderle

當然，因爲所有更小的素數已經找到，所以跳到p ** 2。我會改變它謝謝 – 2012-02-15 03:49:22

StopIteration沒有什麼錯，確實這是發電機的預期行爲。

我會說這實現更Python（不一定是更有效）：

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)))

Python的對我來說意味着清晰，簡潔，易讀，使用語言的優勢。雖然我可以看到你的實現是某種篩選，但我只知道這些算法的經驗。上面的實現可以直接讀取爲對可分性的直接測試。

注：沒有在接口微小的差別，您的實現將產生質數< = N，而我的實現將產生質數<ñ。很顯然，這可以輕鬆地和簡單地改變（只需將n修改爲函數體中的n + 1），但是我認爲生成素數更接近於pythonic，但不包括n與方法更一致，比如說，range()內建作品。

編輯：只是爲了好玩

這裏是一個至少 Python的實現，而且可能非常低效太:)

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)

我稱此爲至少Python的，因爲如果您之前沒有看到過這個訣竅，那麼您可能會在一段時間內摸不着頭腦，弄清楚它是如何工作的！

來源

2012-02-15 04:46:21 wim

謝謝隊友。是的，一旦n變得比1000大得多，它會變得非常慢，但很容易閱讀。 – 2012-02-15 04:57:39

注意：我只是想回答_pythonic_，如果你對python中的_fastest_方法感興趣，這個問題已經很好的覆蓋了[here]（http://stackoverflow.com/questions/2068372/fastest-way-to -list-全素數 - 低於N合蟒蛇）。 – wim 2012-02-15 05:02:58

是的，我會寫這樣的東西，如果我很快需要一些小素數，或者如果我有0記憶。我已經用你的想法提交了另一個答案，這個答案不像pythonic，但稍微有效一些。 – 2012-02-15 08:55:03

這是另一個由@wim驅動的pythonic解決方案，但您可以看到它比第一個方法稍慢。

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"

來源

2012-02-15 08:55:47

imp是'get_primes'指的是這裏？ – wim 2012-02-16 03:22:17

我的問題。如果你添加，如果p * p <= n，你會得到0.025。 wim，我沒有嘗試你的，我認爲它會很慢:) – 2012-02-16 04:44:46

是的，我認爲它可能會慢大約500倍，大聲笑 – wim 2012-02-16 05:18:01

是這個素數發生器pythonic

回答

相關問題