LeetCode-计数质数
创始人
2024-12-29 08:36:27
0

计数质数

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

相关内容

热门资讯

10分钟辅助挂!搜圈麻将假不假... 10分钟辅助挂!搜圈麻将假不假“详细透视辅助助手教程”原来真的有挂,您好,搜圈麻将假不假这款游戏可以...
记者发布!福建十三水 辅助器(... 记者发布!福建十三水 辅助器(透视)透视辅助神器(2023已更新)(哔哩哔哩);1、福建十三水 辅助...
6分钟实锤!博雅红河棋盘外 挂... 您好,博雅红河棋盘外 挂这款游戏可以开挂的,确实是有挂的,需要了解加微【757446909】很多玩家...
八分钟辅助挂!微乐陕西麻将小程... 八分钟辅助挂!微乐陕西麻将小程序有猫腻吗“详细透视辅助脚本教程”原来真的有挂1、下载好微乐陕西麻将小...
必备科技!多乐够级捕鱼辅助软件... 必备科技!多乐够级捕鱼辅助软件(透视辅助)透明挂透视辅助挂(2023已更新)(哔哩哔哩)1、多乐够级...
让我来分享经验!胖猪竞技有外挂... 让我来分享经验!胖猪竞技有外挂没(辅助)确实存在有挂(2026已更新)(哔哩哔哩)胖猪竞技有外挂没辅...
七分钟攻略!七彩云南游戏有外 ... 七分钟攻略!七彩云南游戏有外 挂吗,wePoke原来真的是有挂,wpk教程(有挂细节)1)七彩云南游...
交流学习经验!老友广东麻将来牌... 交流学习经验!老友广东麻将来牌规律(透视)外挂透视辅助插件(2024已更新)(哔哩哔哩)1、在老友广...
13钟辅助挂!闲来贵州麻将可以... 13钟辅助挂!闲来贵州麻将可以挂吗“详细透视辅助app教程”原来真的有挂是一款可以让一直输的玩家,快...
9分钟攻略!乐乐上海麻将有没有... 9分钟攻略!乐乐上海麻将有没有挂,impoker本来有挂,黑科技教程(有挂教程)乐乐上海麻将有没有挂...