204-计数质数

LeetCode 204. 计数质数

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

示例 1：

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7

method 1

直接遍历计算每个数是否是质数

bool isPrime(int x) {
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}
int countPrimes(int n) {
    int res = 0;
    for (int i = 2; i < n; i++) {
        if (isPrime(i)) res++;
    }
    return res;
}

method 2: 埃氏筛

如果 $x$ 是质数，那么大于 $x$ 的 $x$ 的倍数 $2x,3x,\ldots$ 一定不是质数

设 isPrime[i] 表示数 i 是不是质数，如果是质数则为 1，否则为 0。从小到大遍历每个数，如果这个数为质数，则将其所有的倍数都标记为合数（除了该质数本身），即 0，这样在运行结束的时候我们即能知道质数的个数

还可以继续优化，对于一个质数 $x$，如果按上文说的我们从 $2x$ 开始标记其实是冗余的，应该直接从 $x^2$ 开始标记，因为 $2x,3x,\ldots$ 这些数一定在 $x$ 之前就被其他数的倍数标记过了，例如 2 的所有倍数，3 的所有倍数等

int countPrimes(int n) {
    vector<int> isPrime(n, 1);
    int res = 0;
    for (int i = 2; i < n; i++) {
        if (isPrime[i]) res++;
        if ((long)i * i < n) {  // 会溢出
            for (int j = i * i; j < n; j += i) {
                isPrime[j] = 0;
            }
        }
    }
    return res;
}