计数质数
给定整数 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)
。