阅读量:1
计数质数
给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
- 示例 1：
- 输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。 示例 2： - 输入：n = 0
输出：0 示例 3： - 输入：n = 1
输出：0
提示：
- 质数：只能被1和它本身整除的数为质数，0和1不是质数。
- 0 <= n <= 5 * 106
问题剖析
核心问题就是如何高效率的判断一个数是不是质数。
分析
假如一个数n可以被x整除，商为y，那么x和y中的较小的一个数肯定小于等于n^0.5（也就是n的平方根），所以判断一个数是否为质数，只需要遍历2 - n^0.5之间的数能否被n整除即可，如果可以整除那么n就不是质数，否则就是质数。
撸代码
class Solution: def countPrimes(self, n: int) -> int: def isPrimes(num: int) -> bool: '判断数字num是否为质数' i = 2 while i*i <= num: if num % i ==0: return False i += 1 return True count = 0 for i in range(2,n): if isPrimes(i): count += 1 return count 首先遍历小于n的数字，挨个判断每个数是否为质数。
时间复杂度：
- 外部循环：遍历从 2 到 n-1 的所有数字，时间复杂度为 O(n)。
- 内部循环：对于每个数字 i，isPrimes 函数检查是否存在一个小于等于 sqrt(i) 的因子。对于每个 i，这个检查的时间复杂度为 O(sqrt(i))。由于 i 的范围是 2 到 n，平均来看，内部循环的时间复杂度可以粗略估计为 O(sqrt(n))。
然而，更精确地，内部循环的总时间复杂度是所有 sqrt(i) 的和，即 (\sum_{i=2}^{n-1} \sqrt{i})。这个求和可以近似为 (\int_{2}^{n} \sqrt{x} dx = \frac{2}{3}(n^{3/2} - 2^{3/2}))，因此总的时间复杂度为O(n^(3/2))。
空间复杂度
算法中并没有使用额外的大型数据结构，除了几个变量用于计数和迭代。因此，空间复杂度为 O(1)，即常数空间复杂度
更优解法：埃拉托斯特尼筛法
class Solution: def countPrimes(self, n: int) -> int: if n < 2: return 0 l = [1]*n l[0] = 0 l[1] = 0 for i in range(2, int(n**0.5+1)): if l[i] == 1: l[i*i:n:i] = [0] * ((n-1-i*i)//i+1) return sum(l) 解法分析：
默认所有数都是质数，并将默认状态（1：质数，0：不是质数）保存在数组，然后查找不是质数的数字。
如题需要查询所有小于n的非负整数质数，那么如果n不是质数，那么n肯定可以被小于等于n0.5的数整除，同理，如果一个小于n的数不是质数，那么它肯定可以被被小于等于n0.5的某个数整除，所以我们只需遍历2 - n^0.5之间的数，并找出这些数的整数倍的数字（不是质数的数字），并修改数字中的状态，最后计算数组的和就是小于n的质数的个数。
时间复杂度
- 初始化阶段：初始化列表 l 的时间复杂度为 O(n)，因为需要设置每个元素的初始值。
- 筛法遍历：算法从 2 开始，到 sqrt(n) 结束，对于每个未被标记为合数的数字 i，它将从 i*i 开始，每隔 i 个数标记为合数，直到超过 n。每个合数最多被其所有质数因子标记一次，因此，筛法的总时间复杂度接近于 O(n log log n)。
- 更具体地说，对于每个质数 i，算法执行 O(n/i) 次操作（即标记 i 的倍数）。由于所有小于 n 的质数的倒数之和近似为 log log n，因此总时间复杂度为 O(n log log n)。
综合以上，整个算法的时间复杂度为 O(n log log n)。
空间复杂度
算法使用了一个长度为 n 的列表 l 来存储每个数字是否为质数的信息，因此空间复杂度为 O(n)。
