素数（质数），是面试中经常会被问到。计算机中，最常用到素数的应该是密码相关与Hash相关的。今天我们来讲一下素数筛选算法，这是非常常见的一个面试题目，像BAT、华为、360等公司的算法编程题都出现过这个题目。我们今天来讲一下这个算法。我们来看一看这个题目：
输出10万以内的所有素数。
我们更具素数的定义，一个数如果只有1与它本身两个约数，那就是质数。也就是如果一个数能整除1与他本身之外的其他数 ，它就不是质数，于是我们有了下面的算法。
（因为有人留言说看不懂java的代码。。。我晕。。于是这一期用下C++好咯）
这个算法是，对于1到n的每一个数，我们枚举所以小于n的数，看一看能否整除。这个算法的复杂度是O(n*n）。不过因为存在break,所以并没有这么多~
那么，我们有没有什么地方可以进行算法优化呢？像100， 100 / 2 = 50, 100 / 5 = 20, 100 / 10 = 10。我们发现，我们最多只用校验到sqrt(i)，因为如果i能整除x，x>sqrt(i)，那么i / x 一定小于sqrt(i)。
在这个基础上，我们能够将算法复杂度降到O(n*sqrt(n))；
我们再来思考如何进行优化，我们先考虑一个问题，如果i不能整除2，那么i肯定不能整除4,6,8,10。。。也就是，如果i不能除以一个质数x,那么对于质因素含有x的所有数，i都不能整除。也就是，我们只需要判断i能否除以质数即可。
从上面的代码来看，我们需要进行优化，我们需要一个临时的数据结构把那些质数都存起来。然后每次枚举的时候，将这些素数取出来，判断能否整除。
好了，到目前为止这个算法已经很高效了，但这个复杂度很难算，复杂度为O(k*n)，k为小于n的素数的个数，因为break存在，实际复杂度远低于这个。。。
我们再来想想看这个算法怎么优化。（尼玛，竟然还能优化）。我们发现，如果一个数i能够整除11，那么i+1,i+2,i+3..i+10必定不能整除11。别小看这10个步奏，如果这个素数是991，我们就减少了（n/991）* 990次运算，如果是更大的素数，那么就更节省了。苍蝇腿也是肉。。。
那么我们如何来实现呢？感觉从原有的代码上很难进行改造。所谓不破不立，我们换一种思路，如果x是一个素数，那么2*x,3*x,4*x..k*x都不是素数。
我们怎么来实现呢？
我们来解释下这个代码，一开始把所有的数都默认是素数，然后开始枚举，如果某个数是素数，那么2*i,3*i,4*i都是非素数。
这个算法的复杂度是多少呢，N / 2 + N / 3 + N / 5 + N / 7 + .. N / sqrt(N)。这个已经非常接近线性的时间了！！
然后这个算法我们还能够再优化。。不过接下来优化的算法就不介绍了。因为其实也只是在常数上进行优化。有兴趣的话大家可以了解一下。这个优化的算法名称大概可以叫做（快速素数筛选法）。
总结：
今天我们逐步分析，讲解了素数筛选的算法。不知道亲是否已经理解了呢，实际应用中，我们还是要根据现实情况进行选择。
不知道大家是否喜欢这种逐步优化的算法讲解方式呢？还是希望直接讲最终的解法？
欢迎大家关注我的头条号，也可以关注我的微信公众号（ddpcyh）,后续会提供算法学习资料，一起来学习算法,一起来学习数据结构。