首先明白一下什么是素数，素数又名质数，除了2以外就是它本身只能拆分成1和自身相乘而的来的数，如7就是一个素数，他只能由1*7得到，而6不是一个素数，因为它既可以由1*6得到，也可以由2*3得到。

那么知道一个素数的概念，我们便有了一个最朴素的方法求解，即从2~n，每一个数i进行一个判断，这个数字i从2到i-1之间，是否存在一个数字可以与之求余=0的情况，如果没有，则这是一个素数。

一个简单的优化就是，在筛选的时候将判断数据的上届使用sqrt开平方的方式简化判断数据，使用6这个数字就可以很好理解，sqrt(6)约等于2.4，取整后就是2，那么存在一个2*3=6可以满足，这与求完整的数据是一样的，只不过更加高效。

此外，朴素方法一些变种可以间接性的增加处理速度，但基本上都是保持在这个复杂度了。

这里要注意一个Python的问题，我们采取List进行存放素数，然而Python的List的空间限制原因，导致我们求到大概3*10^4大小的数字的同时会发生一些溢出现象，这个时候是没有报错的，可以有两个解决的思路，这里就不帮助解决了（不然偏题）

埃式筛法的思想是：对于不超过 n 的每个非负整数 p，删除 2*p, 3*p, 4*p,…，当处理完所有数之后，还没有被删除的就是素数。

我们可以从2开始，从小到大扫描每个数x,把x的倍数x*2,x*3,…x*(N/x)标记为非质数【此处其实可以优化，不用从2倍开始，因为对于每个数x,x的2倍，3倍都会被2,3，.. 0 # 求素数函数。 def primes(): yield 2 it = _odd_iter() # 初始序列 while True: n = next(it) yield n it = filter(_not_divisible(n), it) # it在不断的next调用中，进行筛选。 # 输出100000以内的所有素数,速度稍微快一丢丢： for n in primes(): if n < 100000: print(n, end=' ') else: break

这份代码采取利用生成器——filter()筛选函数进行过滤，这样写比较直观而且filter过滤的速度相当快，但如果基础不是很好可以参考一下这个C语言版本的，较为容易理解。