算法-计数质数

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法-计数质数，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1795字，纯文字阅读大概需要3分钟。

内容图文

算法-计数质数

1 题目概述

1.1 题目出处

https://leetcode-cn.com/problems/count-primes/

1.2 题目描述

2 暴力枚举

2.1 思路

根据质数性质：只能被1和他本身这两个数整除的数称为质数。

2.2 代码

class Solution {
    public int countPrimes(int n) {
        int result = 0;
        if(n < 2){
            return result;
        }
        for(int i = 2; i < n; i++){
            if(isPrime(i)){
                result++;
            }
        }
        return result;
    }

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

2.3 复杂度

3 暴力枚举-优化

3.1 思路

根据质数性质：只能被1和他本身这两个数整除的数称为质数。

但还可以考虑：

• 提前结束筛选
  
  代码中i * i <= n即为最多只考虑开方数。比如我们这里命 a = i, b = i 。如果a 继续增大，则如果 c = n 整除 a，那么c 必然小于 b ，但 b 此时 小于 a了，肯定已经被判断过了。
• 最先考虑是否能被2整除，如果能则为合数；否则从3开始，每次加2，判断是否整除。
  因为只要不能被2整除，则肯定不能被其他偶数整除。只需要判断其他奇数即可。

3.2 代码

class Solution {
    public int countPrimes(int n) {
        int result = 0;
        if(n < 2){
            return result;
        }
        if(n > 2){
            result++;
        }
        for(int i = 2; i < n; i++){
            if(isPrime(i)){
                result++;
            }
        }
        return result;
    }

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

3.3 时间复杂度

4 埃氏筛

4.1 思路

不需要将合数的倍数标记为合数的原因是，合数的倍数肯定已经被该合数的质因数某个倍数标记过了。

4.2 代码

class Solution {
    public int countPrimes(int n) {
        if(n < 2){
            return 0;
        }
        if(n == 2){
            return 0;
        }
        int result = 0;
        int[] primes = new int[n];
        Arrays.fill(primes, 1);
        for(int i = 2; i < n; i++){
            if(primes[i] == 1){
                result++;
                // 防止i * i 超过 Integer.MAX_VALUE，所以转为long来比较
                if((long) i * i >= n){
                    continue;
                }
                for(int j = i * i; (j > 0) && (j < n); j += i){
                    primes[j] = 0;
                }
            }
        }
        return result;
    }
}

4.3 复杂度

5 线性筛

5.1 思路

5.2 代码

5.3 时间复杂度

参考文档

• LeetCode官方-计数质数解法

内容总结

以上是互联网集市为您收集整理的算法-计数质数全部内容，希望文章能够帮你解决算法-计数质数所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---