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

zlzyp

　　一般，构造一个含有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)
　　优化后，不再有先添加（prime.append()）再移除（prime.remove()）的操作，而是使用flag标志对质数进行标记，节省了运算量。
　　方法直接运用已建立的质数表作为运算参数，减少了无谓的计算量。
　　
　　在较少数据量时，第一种方法对列表的操作更少，会有一定优势。
　　而在更大量数据下，第二种方式会节省大量运算与缓存空间，适用范围更广。
　　
　　更进一步，当我们需要判断一个更大的数是否是质数（如判断一个1.1E16<x<1.2E16的数x）时，用已求得的质数表进行递归运算是种合适的思路。