埃拉托斯特尼算法（埃氏筛）【简单】
核心思想
筛除合数，留下素数：
若x是素数，那么x的倍数一定不是素数，那么这些数就可以直接排除，不必后续再次逐一遍历来降低效率。
既然要记录x的倍数都不为素数，显然我们在进行筛除之前就要创建一个容器来保存所有数（指要求范围的所有数）是否为素数的状态。
那么我们就通过一个数组isPrime[]来实现，如果数i为素数，那么isPrime[i]则为1，否则为0；
然后我们便从小到大遍历，若数为素数，则将其倍数（不包括该素数本身）都标记为合数（即数组对应下标值设为0）；
如此一来，我们遍历完后只要看数组值为1的就是素数，那么记录素数数量甚至输出所有素数等操作都将变得游刃有余了。
正确性说明
首先我们通过上述的基本思想我们可知这个算法就是把里面的合数挑出来标记为0,那么其实在数组创建时我们就是先全都标记为1的，即先全认为是素数，然后通过算法所筛出的确定的素数再来跳出合数，标记为0，故全程数组的数就是一直在从1变为0，也就是开始说的从中挑出合数。那么这个方法就显然不会将质数标记成合数（即从这个方法的感觉中就可确定：质数不会轻易标记成合数，但合数可能不会被发现从而被当作素数）
而我们刚拿到这个方法时难免会感到一种不确定感：为什么我一定能够确定遍历到某个素数（即数组值为1）时它一定就是素数呢？会不会它本是合数，只是之前的遍历操作中未将它发现，从而有了漏网之鱼呢？
我们现在来一探究竟：首先，这个方法一定不会将素数标记为合数。当我们从小到大遍历时，若数x是合数，那么根据合数的性质知x至少有一个素数因数（注意1不为素数），我们就记为y，那么从小到大遍历中我们会在x之前先遍历到y，那么在把y的倍数标记为合数的时候定然就会把x标记为了合数，因此不会出现漏网之鱼的合数未被标记，导致误成为素数的情况。
优化
当我们知道了它的正确性的成立原因道理，接下来的优化操作就容易理解了：
对于质数x，若按先前的方式从2x开始标记为合数其实是会有重复操作的，会不会这个2x在之前就已经被标记为了合数的呢？如果是，那我这次的操作岂不是白干了！？
那我们现在就得研究从什么时候开始标记既不会遗漏，也不会重叠：
其实从上一节中的合数 x 至少有一个素数因数 y我们其实就能猜到：在x*x之前数都不需要标记，因为之前的数k*x 其中 k 取值从 2 ~ x-1中的k是小于x的，那么有两种情况：一是k为质数，那么在遍历到k时k*x一定会被标记为合数的；二是k不为质数，那么也是照前面说的一样，k必有一个素数因数y，那k*x也必会有一个素数因数y，那显然在遍历到y时k*x一定就会被标记为合数的。
而x*x又是只有因数x和1，所以其只能靠x来标记为合数，故从x*x开始标记既保证了之前的已经被标记，也保证了开始的x*x只能靠x标记，因此从x*x开始就是最优“起点”。
算法步骤
- 初始化筛子：创建长度为
n + 1的bool类型（int也未尝不可）数组isPrime[n + 1]，其中数组的索引就代表对应的数字，而数组的值则表明其对应数字是否为素数（比如isPrime[11] = 1就代表数字11为素数），然后数组初始时全为true，但注意要把下标0、1位置设置为false（这两个数规定了不为素数） - 筛除合数：从
i = 2遍历到 $\sqrt{n}$ ，若isPrime[i] = true，则把i的所有倍数记为false。当然优化后就是从i*i开始标记为false。 - 结果提取：遍历结束后，值为
true的索引即是1 ~ n之间的所有素数。
示例代码 （C++）
class Solution { public: int Primes(int n) { if (n <= 2) return 0; if (n == 3) return 1; vector<bool> IsPrime(n, true); for(int i = 3; i * i < n; i += 2){ if(IsPrime[i]){ for(int j = i * i; j < n; j += i){ IsPrime[j] = false; } } } // 此时容器内的所有数都筛选完了，接下来就可按照题意进行想要的操作 // 如果为了进一步高效，甚至可以在进行筛选的过程中同步进行一些操作，但一定要保证在操作时所操作的数字已经筛选过了 };