寻找石家庄网站建设,网站建设在后台哪里查看,wordpress 2.0 下载,网页模版下载器计数质数
给定整数 n #xff0c;返回 所有小于非负整数 n 的质数的数量 。 示例 1#xff1a; 输入#xff1a;n 10 输出#xff1a;4 解释#xff1a;小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。 示例 2#xff1a; 输入#xff1a;n 0 输出#xff1a;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 2while i*i num:if num % i 0: return Falsei 1return Truecount 0for i in range(2,n):if isPrimes(i): count 1return count首先遍历小于n的数字挨个判断每个数是否为质数。
时间复杂度
外部循环遍历从 2 到 n-1 的所有数字时间复杂度为 O(n)。内部循环对于每个数字 iisPrimes 函数检查是否存在一个小于等于 sqrt(i) 的因子。对于每个 i这个检查的时间复杂度为 O(sqrt(i))。由于 i 的范围是 2 到 n平均来看内部循环的时间复杂度可以粗略估计为 O(sqrt(n))。 然而更精确地内部循环的总时间复杂度是所有 sqrt(i) 的和即 (\sum_{i2}^{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 0l [1]*nl[0] 0l[1] 0for i in range(2, int(n**0.51)):if l[i] 1:l[i*i:n:i] [0] * ((n-1-i*i)//i1)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)。
