以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 =
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
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）时，用已求得的质数表进行递归运算是种合适的思路。
页:
[1]