我搞了一个下午和一个晚上，网上的博客、视频讲得不清不楚，真的感觉很难！！！下面是自己的理解，不保证没问题！
以下代码按照该题来写：模板题：204. 计数质数。
埃氏筛算法中，同一个合数会被多个质数标记（例如 45 这个数，它会同时被 3,5 两个数标记为合数），线性筛则保证每个合数只会被其最小质数因数标记。很难搞懂，如果实在搞不懂，没必要花精力，因为复杂度和埃氏筛差别不大。
时间复杂度：\(O(n)\) [1]；
空间复杂度：\(O(n)\)；
示例代码：
class Solution {
public:
int countPrimes(int n) {
vector<bool> isNotprimes(n); // 标记是否为合数
vector<int> primes; // 存遍历到的质数，使用vector会很慢
int ans = 0;
for (int i = 2; i < n; ++i) {
if (!isNotprimes[i]) { // 质数
++ans;
primes.push_back(i); // 添加到质数数组
}
/**
* 标记i的倍数为合数：“j < prime.size()”条件可以省略，因为：
* - 如果i是质数，那么if语句一定在最后一个元素成立，
* - 如果i是合数，那么一定会小于它的质数整除，由于小于它的质数都被保存到数组里边
*/
for (int j = 0; (long long)i * primes[j] < n; ++j) {
isNotprimes[i * primes[j]] = true; // 如果i为合数，且 “i的最小质因子*i” 未越界，则 “i的最小质因子*i” 得到的合数一定能被筛掉
/**
* - 此条件的作用：primes数组中的质数是递增的，当“i%primes[j]==0”成立（i能被primes[j]整除），
* 那么 (i*primes[j+1]) 这个合数肯定也可以被 (primes[j]) 筛掉，
* 因为i中的含有 (primes[j])，也就是 i*primes[j+1]=(k*primes[j])*primes[j+1]，
* 所以，当“i%primes[j]==0”成立时，需要终止，否则当i遍历到 (k*primes[j+1]) 时，
* i*primes[j+1]，也就是((k*primes[j])*primes[j+1])会再次被筛掉。
*/
/**
* - 那当前遍历的i如果是合数，会不会在之前没被筛掉？
* 不会，假设一个合数为z，它的最小质因子为x，x*y=z（y为另一个因子，可能为质数也可能为合数），必有x<=y，
* 由于x>1，因此有 y<z，当i遍历到y，分两种情况：
* （1）当y质数，那么(i%primes[j]==0)的成立条件为 primes[j]=y，因此x必被primes[j]遍历到，也就是z必被标记。
* （2）当y为合数，那么此时y可类比成当前的z，也可分解成两个数x_y*y_y=y（下划线后面的y表示是y的因子），
* 由于任何合数都能被分解成多个质因子相乘，y是合数也是z的因子，因此y的因子也是z的因子，
* 由于x是z的最小质因子，因此必有x<=x_y。
* 由于对于一个合数y，只要 “x_y*y<n” ，也就是循环的条件成立，那么 x_y 必被primes[j]遍历到，
* 而 x<x_y，primes数组又是从小到大遍历，因此 x 必被primes[j]遍历到，也就是z必被标记。
*/
if (i % primes[j] == 0) { // 整除中断，保证合数被最小的质因数整除
break;
}
}
}
return ans;
}
};
线性筛理论上比埃氏筛快，但实际上差不了多少（一个是\(O(n)\)，一个是\(O(n\cdot loglogn)\)），但是如果代码中的数组使用了vector，由于线性筛算法涉及到多次数组存取（vector访问速度比原生数组慢）和内存的动态分配，可能会比埃氏筛慢不少。 ↩︎