是这个素数发生器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

回答

相关问题