LeetCode刷题【204】计数质数

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

 

示例 1：

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

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0

 

提示：

• 0 <= n <= 5 * 106

题解，求小于n的质数，一上来一看好像挺简单，还简单题。

挨个算嘛，暴力求解

class Solution {
    public int countPrimes(int n) {
        if (n<2){
            return 0;
        }
        if (n==2){
            return 0;
        }
        List<Integer> list = new ArrayList<>();
        list.add(2);
        boolean isPrimes = true;
        for (int i = 3; i < n ; i++) {
            isPrimes = true;
            for(int num : list){
                if (i % num == 0){
                    isPrimes = false;
                    break;
                }
            }
            if (isPrimes){
                list.add(i);
            }
        }
        return list.size();
    }
}

结果直接超时，心想不至于吧。。还能超时。然后找了张纸画了个矩阵图看了看。

如下

于是萌生了一个想法，我只要把小于n的数去掉了这些能用乘积法求出来的数，剩下的数字不就是质数了么。这过程中还有一个细节点，比如2×6=12,3×4=12，这俩是重复的，需要判断处理下。于是得到了代码如下：

class Solution {
    public int countPrimes(int n) {
        if (n<=2){
            return 0;
        }
        int count = 0;
        int tmp = 0;
        int[] res = new int[n];
        for (int i = 2; i*i < n; i++) {
            for (int j = i; j*i < n; j++) {
                tmp = i*j;
                if (res[tmp] == 0){
                    res[tmp] = 1;
                    count++;
                }
            }
        }

        return n - count - 2;
    }
}

最终结果需要额外减去2是因为前面1、2的结果都为0，需要额外减去。

解答成功:
执行耗时:139 ms,击败了8.31% 的Java用户
内存消耗:56.4 MB,击败了17.00% 的Java用户

结果好像不太理想，还能再优化？

class Solution {
    public int countPrimes(int n) {
        if (n == 0 || n == 1) return 0;
        int[] arr = new int[n];
        arr[0] = 1;
        arr[1] = 1;
        int count = 0;
        for (int i = 2; i * i < n; i++) {
            if (arr[i] == 1) continue;
            for (int j = 2 * i; j < n; j += i) {
                if (arr[j] == 0){
                    arr[j] = 1;
                    count++;
                }
            }
        }
        return n - count - 2;
    }
}