☆打卡算法☆LeetCode 204. 计数质数 算法解析

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定整数n，返回所有小于整数n的质数的数量。”

题目链接：

来源：力扣（LeetCode）

链接： 204. 计数质数 - 力扣（LeetCode）

2、题目描述

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

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

示例 2：
输入： n = 0
输出： 0

二、解题

1、思路分析

题意要求出所有小于整数n的质数的数量。

统计质数数量有很多方法，直观的思路是枚举每个数判断是不是质数。

首先来看一下质数的性质：

• 在大于的1的自然数中，除了1和它本身以外不再有其他因数的自然数。

根据质数的性质，对于每个数x，可以枚举[2,x-1]中的每个数y，判断y是否为x的因数，但是这样时间复杂度过高，需要考虑其他方法。

考虑到如果y是x的因数，那么\frac{x}{y}必然也是x的因数，因此只要校验y或者\frac{x}{y}即可。

进一步思考，只需要校验y和\frac{x}{y}之间的较小值，较小值会落在 [2,\sqrt{x}] 的区间中，因此只需要枚举 [2,\sqrt{x}] 区间中中的所有数即可。

2、代码实现

代码参考：

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

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

3、时间复杂度

时间复杂度：O(n\sqrt{x})

单个数检查的时间复杂度为O(\sqrt{x})，一共要检查O(n)个数，因此总时间复杂度为O(n\sqrt{x})。

空间复杂度：O(1)

只需要常数级的变量空间。

三、总结

枚举每个数字是否为质数。

判断素数的方法参考定义，对于某个数字 n，i 从 2 开始枚举判断是否满足 n % i == 0 ，如果找到了 n 的因子，就返回 false。

注意 i 遍历到最大 \sqrt{n} 即可。

因为 n 如果不是质数，那么至少有一个因子是小于等于 \sqrt{n} 的。