https://leetcode.cn/problems/count-primes/
204 给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
这题如果用对每个数i，让j从2遍历至sqrt(i)是否存在j，使得i % j == 0（被j整除），是最容易的想到的，但会超时。
看了埃拉托斯特尼筛法（Sieve of Eratosthenes，简称埃氏筛法）后，有很多简化和优化的写法，发现有些不易理解，这里提供一个最易理解的，但不是最优的写法：
class Solution {
public:
int countPrimes(int n) {
// 对n，遍历1到n的数，偶数肯定不是质数，3、5等质数的倍数肯定不是，全部标注完后剩余的就是质数
if (n < 2) return 0;
vector<bool> prime(n, true);
for (int i = 2; i < n; ++i) { // 从2开始，并标记所有的2的倍数
// if (i & 1) { // 等价于i%2，如果一直去除2的倍数，这里和下边代码重复了，就省略了
// prime[i] = false;
// continue;
// }
if (prime[i]) { // 如果当前数是质数，其倍数肯定不是质数，标注为false
for (int j = 2 * i; j < n; j += i) { // 从i的2倍开始，随后3*i、4*i....
// 可能会重复赋值标记，如i=3时会标注prime[15]为false，到i=5时还会标记一次
prime[j] = false;
}
}
}
// 全部统计完后，看下还多少true的
int count = 0;
for (int i = 2; i < n; ++i) { // 1不是质数，2开始才是
if (prime[i]) ++count;
}
return count;
}
};
从代码注释可看出，对小于n的数都会对其倍数进行判断，且有重复标注的情况，所以可以此进一步优化，减少遍历次数；如n=10时，i=2时已标注4、6、8，i=3时标注了6、9，剩下2、3、5、7就是质数了，所以4以后就不用遍历了，也就是其他写法里的到达i<=sqrt(n)的写法。
class Solution {
public:
int countPrimes(int n) {
if (n < 2) return 0;
vector<bool> prime(n, true);
int s = sqrt(n); // 减少循环次数的写法
for (int i = 2; i <= s; ++i) { // 从2开始，并标记所有的2的倍数
if (prime[i]) { // 如果当前数是质数，标注其倍数肯定不是质数
for (int j = 2 * i; j < n; j += i) { // 从i的2倍开始，随后3*i、4*i....
// 可能会重复赋值标记，如i=3时会标注prime[15]为false，到i=5时还会标记一次
prime[j] = false;
}
}
}
// 全部统计完后，看下还多少true的
int count = 0;
for (int i = 2; i < n; ++i) { // 1不是质数，2开始才是
if (prime[i]) ++count;
}
return count;
}
};
第一次结果：
第二次结果：
