转载

以Python列表特性为切入点的求质数列表的方法

一般，构造一个含有2-x之间所有质数的列表，我们采用最简单的遍历判断质数的方法：

 # 方法一
 1 prime = []  2   3 def is_prime(n):  4     if n <= 1:  5         return False  6     for i in range(2, int(math.sqrt(n)) + 1):  7         if n % i == 0:  8             return False  9     return True 10  11 for i in range(2, x): 12     if is_prime(i): 13         prime.append(i)

这个方法的优势在于逻辑简单，易于想到。

而对于Python非常有特色的列表操作，可以用其特性以更少的步骤获得指定范围的质数：

# 方法二
prime = [2] def list_prime(n):  if n < 2:   print("invalid input")  for i in range(3, n + 1, 2):   prime.append(i)   k = int(math.sqrt(i))   for x in prime:    if i % x == 0:     prime.remove(i)     break    elif x > k:     break

对比第一种方式中，如果遇到质数x，那么每个它前面的小于sqrt(x)的数都会与之求余运算一次，需要消耗较多的计算时间；

第二种方式下，在遇到质数x时，仅仅将其与小于sqrt(x)的质数进行求余运算，可以减少计算时间。

但，相对于运算节省的时间，第二种方式下用到了prime.remove()方法，而这会占用大量运算量，因此进行了优化：

 # 方法二（改进）
 1 prime = [2]  2   3 def list_prime(n):  4     if n < 2:  5         print("invalid input")  6     for i in range(3, n + 1, 2):  7         k = int(math.sqrt(i))  8         flag = True  9         for x in prime: 10             if i % x == 0: 11                 flag = False 12                 break 13             elif x > k: 14                 break 15         if flag: 16             prime.append(i)