leetcode算法题-计数质数

发表于 | 分类于 | 阅读次数: |

题目

本题为leetcode探索初级算法中数学章节的一题

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

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

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnbcaj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

我的解法

看了题目感觉挺简单于是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int countPrimes(int n) {
        int result = 0;
        for (int i = 2; i < n; i++) {
            boolean is = true;
            for (int j = 2; j <= i; j++){
                if(i != j && i % j == 0){
                    is = false;
                    break;
                }
            }
            if(is){
                result ++;
            }
        }
        return result;
    }
}

运行的时候超出了限制。尴尬。

优化版

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
26
27
28
class Solution {
   public  int countPrimes(int n) {
        int result = 0;
        for (int i = 2; i < n; i++) {
            if(isPrime(i)){
                result ++;
            }
        }
        return result;
    }

    public  boolean isPrime(int num) {
        if (num <= 3) {
            return num > 1;
        }
        // 不在6的倍数两侧的一定不是质数
        if (num % 6 != 1 && num % 6 != 5) {
            return false;
        }
        int sqrt = (int) Math.sqrt(num);
        for (int i = 5; i <= sqrt; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
}

主要优化了判断质数的逻辑，根据质数的规律优化了判断。
执行用时: 236 ms，内存消耗: 35.6 MB。
但是运行时间还是太长。

题解版-厄拉多塞筛法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int countPrimes(int n) {
        int result = 0;
        boolean[] b = new boolean[n];   // 初始化默认值都为 false，为质数标记
        if(2 < n) result++; // 如果大于 2 则一定拥有 2 这个质数
        
        for(int i = 3; i < n; i += 2){  // 从 3 开始遍历，且只遍历奇数
            if(!b[i]){  // 是质数
                for(int j = 3; i * j < n; j += 2){
                    b[i * j] = true;    // 将当前质数的奇数倍都设置成非质数标记 true
                }
                result++;   // 质数个数 +1
            }
        }
        return result;
    }
}

利用长度为n的数组记录是否质数的结果。
当a不是质数时，将小于n的且是a的倍数的数字设置为不是质数。
虽然多了额外的空间开销但是耗时仅10ms，快了20多倍。
ps:若n非常大时，可以考虑位图等替换数组。