LeetCode/204. 计数质数

204. 计数质数

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

示例1：

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

示例2：

输入：n = 0
输出：0

示例3：

输入：n = 1
输出：0

提示：

• 0 <= n <= 5 * 106

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

我们从小就知道数学里面判断一个数是否为质数，只需要判断从2到$\sqrt{num}$中是否有数能够被num整除，如果有，那该数就不是质数，如果没有则该数为质数，根据该理论可以很容易写出代码。

具体代码如下：

class Solution {
    public int countPrimes(int n) {
        int result = 0;
        for (int i = 2; i < n; i++) {
            result += isPrimes(i) ? 1 : 0;
        }
        return result;
    }

    private boolean isPrimes(int num) {
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0)
                return false;
        }
        return true;
    }
}

但是该方法时间复杂度很高。考虑到数与数之间的关系，一个数的整数倍必然不是质数，而且当前数前面的倍数肯定已经被判断过了，我们每次只需要从i * i开始即可。

具体代码如下：

class Solution {
    public int countPrimes(int n) {
        boolean[] isPrime = new boolean[n];
        for (int i = 2; i * i < n; i++) {
            if (!isPrime[i]) {
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = true;
                }
            }
        }

        int result = 0;
        for (int i = 2; i < n; i++) {
            if (!isPrime[i])
                result++;
        }
        return result;
    }
}