在 求指定范围内的质数个数 问题中，一般有试除法和筛法两大类。
试除法【时间复杂度为O(n^2)】容易超时。筛法中又有朴素筛、埃氏筛、欧拉筛。虽然欧拉筛【时间复杂度为O(n)】是线性的最优的，但是在理解和写比较复杂。一般用埃氏筛【时间复杂度为O(n loglogn)】就够了，埃氏筛代码简洁、更易理解。且本篇的埃氏筛还有两处细节优化。
埃氏筛原理先假设每个数都是质数。
从 2 开始，2是质数，那么2的倍数：4、6、8、10、12、14、16... 肯定不是质数3是质数，那么3的倍数：6、9、12、15、18、21..... 肯定不是质数4已经被筛去了（即被置为false），不是质数，那么4的倍数肯定被它的因子筛过，所以4不用看，跳过... ...
没有被筛去的一定是质数，因为它没有被比它小的任何一个数筛去，说明它不是任何一个数的倍数，所以一定是质数。
代码#include细节优化using namespace std; #include //Dev C++下memset头文件，vs 2019中不用加 const int N = 1e5; //即 10,0000 bool isPrime[N + 5]; //标记每个数，如果为true，则为质数，否则为合数；这里一定要多开一个空间，否则标记N时，会数组越界而报错 int primes[N + 5]; //存储质数 int cnt = 0; //记录质数个数 void aiPrime() { memset(isPrime,true,sizeof(isPrime)); //先都初始化为真 for (int i = 2;i <= N / i;i++) //注意这里 i <= N / i就可以，解释见后文 { if (isPrime[i]) //如果当前数是质数，那么将它的倍数都标记为 false { for (int j = i * i; j <= N; j += i) { isPrime[j] = false; } } } for (int i = 2; i <= N; i++) //将质数放入primes数组 { if(isPrime[i]) primes[cnt++] = i; } } int main() { aiPrime(); cout << cnt << endl; return 0; }
优化1
现在我们来讨论一下为什么在筛去倍数时，只要 i <= N / i 就可以。
如果是 i <= N，肯定是可以的。那么现在来看 i <= N / i，
以当前质数 i = 109 为例，109的倍数 2 * 109 =218、3 * 109 = 327、4 * 109 = 436、5 * 109 = 545、6 * 109 = 654、7 * 109 = 763、8 * 109 = 872、9 * 109 = 981 这八个数都会被筛去，但是在 2、3、4、5、6、7、8、9 的时候就会被筛掉。
如果 a * b = c （a <= b），那么 a <= sqrt(c) <= b。 所以 c 既会被 a 筛掉，又会被 b 筛掉，所以 c 一定会被 a 筛掉，而不用考虑 b。故 i <= sqrt(c) 就可以了。
有的写法为 i * i <= c，是不推荐的。因为 i * i 容易溢出。虽然换成 除法 是比较慢的，但是很安全。所以 i <= N / i 和 i <= sqrt(N) 这两种写法都是可以的。
【ps: 有的地方写作 i <= sqrt(N) + 1或者是 i <= N / i + 1，其实是大可不必的】
以N = 143为例，按照如上写法，那么i = 12 也参与循环，12的倍数【24、36...12*11 = 132】都会被筛去，可是这些注定被之前筛过。
以N = 169为例，按照如上写法，那么i = 14 也参与循环，14的倍数【28、42...14*12 = 168】都会被筛去，可是这些注定被之前筛过。
以N = 197为例，按照如上写法，那么i = 17 也参与循环，17的倍数【34、51...17*14 = 187】都会被筛去，可是这些注定被之前筛过。
优化2
在取倍数时，不是从2倍(i * 2)开始，而是 for (int j = i * i ; j <= N; j += i) 。
应用找质数（计蒜客：2019 蓝桥杯省赛 B 组模拟赛（一）） 测试平台：计蒜客
