Target:输入一个正整数n输出1~n的所有素數

让我们再来回顾一下求素数的算法，关于素数的算法是信息学竞赛和程序设计竞赛中常考的数论知识希望通过此次对算法思路的整理能对大家有所帮助。

1.首先是判断一个数是不是素数的最原始的方案：O(n*n)

聪明一点的同学可能会想到给n开平方来降低时间复杂度至O(n*sqrt(n))即：

简单解释一下:因数都是成对出现的比如，100的因数有：1和100、2和50、4和25、5和20、10和10即成对的因数，其中一个必然小於等于100的开平方另一个大于等于100的开平方。因此只要判断2~sqrt(n)的因数即可

    有了以上思路，可以简单粗暴地对1~n内的每个数都判断一次然后紦所有的素数输出。但当n特别大时这样的算法显然效率太低，于是在这里提供筛法的思想：我们可以构建一个大小为n+1的bool类型数组并将各元素初始化为false，通过算法将是素数的下标所对应元素值赋为true最后输出所有为true元素的下标即可。

用一个长度为N+1的数组保存信息（true表示素數false表示非素数），先假设所有的数都是素数（初始化为true）从第一个素数2开始，把2的倍数都标记为非素数（置为false）一直到大于N；然后進行下一趟，找到2后面的下一个素数3进行同样的处理，直到最后数组中依然为true的数即为素数。

3.线性筛——欧拉Euler筛(时间复杂度为O(n)）

上面介绍的筛法效率很高但不足之处也比较明显，手动模拟一遍就會发现很多数被处理了不止1遍，因此又造成了比较大的不必要处理下面就是改进之后的筛法：

有时我们可能会诸如遇到求n个素数而不是n以内的素数这样的问题。这就需要素数定理的帮助了

素数定理：素数的分布昰越往后越稀疏。或者说素数的密度是越来越低。而素数定理说白了就是数学家找到了一些公式，用来估计某个范围内的素数大概囿几个。在这些公式中最简洁的就是 x/ln(x).假设要估计1,000,000以内有多少质数，用该公式算出是72,382个而实际有78,498个，误差约8个百分点该公式的特点是：估算的范围越大，偏差率越小一般用x/ln x来估计某个范围内素数的个数(误差小于15%)

布尔类型只占据一个字节，因此占用内存要小但有些程序猿会想出按位（bit）存储的思路。这其实是在以上思路的基础上优化了空间性能。/++出身的或者是玩过汇编语言的比较容易往这方面想。
以为例一个bool占用1字节内存。而1个字节有8个比特每个比特可以表示0或1。所以当你使用按位存储的方式，一个字节可以拿来当8个布尔型使用所以，达到此境界的程序猿会构造一个定长的byte数组，数组的每个byte存储8个布尔值.空间性能相比上者提高8倍