我们知道第一个质数是 2、第二个质数是 3、第三个质数是 5……那第 2020 个质数是多少？
当看到这种寻找质数的问题，很多人第一时间想到的便是二重循环暴力查找。但如果要找第2020个质数、第9999个质数，这种暴力方法查找的速度就太慢了。
这个时候就可以使用筛法来提高运行速度，本文介绍的是埃氏筛法。因为质数的倍数一定不是质数，因此将质数的倍数直接标记成合数，标记后列表中没被标记且没记为质数的最小的那个数一定是质数（1除外），以此达到快速筛选质数的目的。
例如：筛选1-10之间的质数。
1不是质数，直接看2-10。
（质数标记为红色，合数标记为蓝色）
图 2.5 第四次标记
代码：
| def eratosthenes(n):lis = [0 for i in range(n + 1)]# 初始化为0，0表示质数，1表示合数lis2 = []
# 存质数 for i in range(2, n + 1): if lis[i] == 0: # 如果没有被标记就加到Lis2 lis2.append(i) for j in range(i * 2, n + 1): if j % i == 0: # 记录合数 lis[j] = 1 return lis2 |
虽然和暴力查找相比，埃氏筛快了很多。但是如果大家仔细看埃氏筛法标记合数的情况可以很清楚的看到有很多数字是被重复标记的。比如10，质数是2时会标记，质数是5时也会标记。那么我们是不是可以找一个办法解决重复标记的问题？
转载请注明：XAMPP中文组官网 » Python经典案例实践|埃氏筛法求质数