終ノ空

最近在学习MIT的在线计算机科学入门课程，碰到了生成质数的问题。
所谓的质数，就是在大于1的正整数中，因数只有1和其本身的整数。比如2，3，5……。
第一反应之下，我只想到最笨的办法：

def genPrimesDirectly():
  '''Generate Prime Numbers using Python generator.
    It is the worst economic method I can think of. The complexity should be O(nlog(n))
    Written by aresowj on 08/09/2015'''
  n = 2		#First number
  yield n
  while True:
    n += 1						#Start from 3
    for i in range(2, n):		#Calculates every number from 2 to n-1 to confirm if any factor of n
      if n % i == 0:
        break
      elif i == n - 1:		#If i is the last number in the sequence and i is not a factor of n, n is a prime number. Then yield it.
        yield n

能够改进的地方还是有的，那就是缩小在判断每一个数字时用来求余的范围。在笨办法里，程序将用 [2, n-1] 这个区间里的每个数对n求余，如果发现n能够被区间内的某个数除尽，则判断n不是质数，从而跳到下一个n的判断中。 继续阅读关于生成质数 (Prime Number) 的思路