计数质数

发表于 | 分类于

题目：（LeetCode.204）统计所有小于非负整数 n 的质数的数量

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

质数：在大于1的自然数中，除了1和它本身以外不再有其他因数。算法中的基本判断思路是：对于正整数n，如果用2到 $\sqrt n$ 之间到所有整数去除，均无法整除，则n为质数

暴力解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int countPrimes(int n) {
        int count = 0;
        for (int i = 1; i < n; i++) {
            if (isPrime(i)) {
                count++;
            }
        }
        return count;
    }

    private boolean isPrime(int n) {
        if (n <= 3) {
            return n > 1;
        }

        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

这种方法逻辑原理没有问题，但是时间复杂度较高，在LeetCode中提交显示时间超时（Time Limit Exceeded）。

通过思考质数的定义，可以发现，如果某一个数为质数，那么这个数的任何整数倍数都不是质数，所以可以通过递推的方式进行判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int countPrimes(int n) {
        if (n < 3) {
            return 0;
        }
        int[] nums = new int[n];
        nums[0] = 1;
        nums[1] = 1;
        for (int i = 2; i < Math.sqrt(n); i++) {
            if (nums[i] == 0) {
                for (int j = i * i; j < n; j += i) {
                    nums[j] = 1;
                }
            }
        }

        int count = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                count++;
            }
        }
        return count;
    }
}