产生质数的迭代器_质数迭代器

      这篇文章介绍两种用python编写质数迭代器的方法。

      第一种方法非常简单：

 def genprime(): yield 2 for n in countodd(1): if isprime(n): yield n

        这个方法的思想是除了2之外，在所有奇数中判断是否为质数。countodd是一个奇数迭代器。可以这样来定义：

def countodd(n): while True: yield n n+=2

       剩下的就是如何来编写isprime方法了。没有捷径可走，只能按照质数的定义老老实实的来穷举。当然我们可以用一个小技巧把复杂度从

O(n)降到O(n^0.5)。

def isprime(n): if n<2: return False for i in range(2,int(math.sqrt(n))+1): if n%i==0: return False return True

      最后，它的总的时间复杂度为O(n^1.5)。

      第二种方法是基于古老的筛选法。筛选法是先列出一定范围内的自然数，然后依次删除2的倍数，3的倍数，5的倍数，······。剩下的就是质数了。

       再次感谢python的迭代器，使我们不必真的去列出这些自然数。否则这又会是一个头疼的问题了。如果你看过这篇文章用python解决 Google Treasure Hunt 2008 Question:Primes，你一定看到过这个方法了。

def sieve(): """Sieve of Eratosthenes, yield each prime in sequence.""" yield 2 D = {} q = 3 while True: p = D.pop(q, 0) if p: x = q + p while x in D: x += p D[x] = p else: yield q D[q*q] = 2*q q += 2

      如果第一次看到这个筛选法，会感觉有点奇怪。因为通常我们编写筛选法时用到的是位集。这里用到的是词典。

      质数的倍数会临时性的当做键值插入到词典中。所以判断依据是如果一个数出现在词典中，那么它一定不是质数。

      因为词典的插入，删除，搜索的复杂度都是O(1)，所以这个方法的效率非常好。每一次执行的时间复杂度是O(1)，总的时间复杂度是O(n)。但是词典中保存的数的总数会随着q的增大而增大，其值大约是q/ln(q)。增长率为下图中的蓝线。红线为n^0.5，绿线为n。