204. 计数质数

一、题目描述

统计所有小于非负整数 n 的质数的数量。

二、解题思路

如果 x 是质数，那么大于 x 的 x 的倍数 2x, 3x ,… 一定不是质数。

不过实际上，对于一个质数 x，应该直接从 x⋅x 开始标记，因为 2x, 3x, … 这些数一定在 x⋅x 之前就被其他数的倍数标记过了。

例如 2x 已经被 2 标记了，3x 已经被 3 标记了。

三、时间复杂度

• 时间 O(n)
• 空间 O(n)

四、参考代码

/**
 * 统计所有小于非负整数 n 的质数的数量
 * @param n 非负整数
 * @return 质数数量
 */
public int countPrimes(int n) {
    if (n <= 1) {
        return 0;
    }
    boolean[] bools = new boolean[n];
    Arrays.fill(bools, true);
    bools[0] = bools[1] = false;
    for (int i = 2; i < Math.sqrt(n); i++) {
        if (!bools[i]) {
            continue;
        }
        for (int sum = i * i; sum < n; sum += i) {
            bools[sum] = false;
        }
    }
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (bools[i]) {
            count++;
        }
    }
    return count;
}