正文
厄拉多塞筛法和普通方法求素数表（python实现）
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
厄拉多赛筛法(sieve of Eratosthenes)：
想要得到一个不大于N的数所有素数，可以先找到不超过根号N的所有素数，设2 = p1 < p2 < ......<pk ≤√N，然后在2,3,4......N里面进行下面的操作：
留下p1 = 2，把p1的倍数全部划掉，
再留下p2 ，把p2 的倍数全部划掉，
继续这一过程，直到留下pk，把pk的倍数全部划掉，
最后留下来就是不超过N的全体素数。
举例：
N = 30 ，则取pk 为5，所以2到5的所有素数为2,3,5
第一遍 留下2，划去2的所有倍数
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
第二遍 留下3，划去3的所有倍数
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
第三遍 留下5，划去5的所有倍数
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
剩余的数就是小于等于30的所有素数，即 2,3,5,7,11,13,17,19,23,29
算法实现：
算法思想来自于上面的介绍，但是并不是严格遵循上面的步骤：
def eladuosai(n):
l = list(range(1,n+1))
l[0] = 0
for i in range(2,n+1):
if l[i-1] != 0 :
for j in range(i*2,n+1,i):
l[j-1] = 0
result = [x for x in l if x != 0]
return result
求小于等于N的所有素数的普通算法：
def sushu(n):
result = []
for x in range(2,n+1):
for y in range(2,x):
if x % y == 0:
break
else:
result.append(x)
return result
时间对比，使用timeit模块测试两个方法的时间，当取n为10000的时候有如下结论：
t1 = timeit.Timer('sushu(10000)',setup='from __main__ import sushu')
t2 = timeit.Timer('eladuosai(10000)',setup='from __main__ import eladuosai')
print('厄拉多塞筛法的时间 ',t2.timeit(1))
print('普通函数的时间 ： ',t1.timeit(1))
厄拉多塞筛法的时间 0.005523548190824634
普通方法的时间 ： 0.7220688150193577
可以看出厄拉多塞筛法的运行时间比普通方法的时间要少很多。
