首页 > 其他分享 >LeetCode-计数质数

LeetCode-计数质数

时间:2024-07-17 17:57:39浏览次数:12  
标签:小于 log int 质数 sqrt 计数 复杂度 LeetCode

计数质数

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

标签:小于,log,int,质数,sqrt,计数,复杂度,LeetCode
From: https://blog.csdn.net/BDawn/article/details/140492872

相关文章

  • leetcode145. 二叉树的后序遍历,递归法+迭代法,全过程图解+步步解析,一点点教会你迭代法
    leetcode145.二叉树的后序遍历,递归法+迭代法给你一棵二叉树的根节点root,返回其节点值的后序遍历。示例1:输入:root=[1,null,2,3]输出:[3,2,1]示例2:输入:root=[]输出:[]示例3:输入:root=[1]输出:[1]递归法还是一如既往的简单。postorder函数是递归函数,用......
  • LeetCode第257题:二叉树的所有路径的Java实现
    摘要LeetCode第257题要求生成二叉树的所有从根节点到叶子节点的路径。本文将介绍两种Java解决方案:迭代法和递归法。1.问题描述给定一个二叉树的根节点,按照从根到叶的顺序遍历所有路径,并将它们作为列表的列表返回。2.示例分析输入:[1,2,3,null,null,4]'输出:[[1,2],[1,......
  • LeetCode 2263. Make Array Non-decreasing or Non-increasing
    原题链接在这里:https://leetcode.com/problems/make-array-non-decreasing-or-non-increasing/description/题目:Youaregivena 0-indexed integerarray nums.Inoneoperation,youcan:Chooseanindex i intherange 0<=i<nums.lengthSet nums[i] to num......
  • LeetCode算法笔记5
    题目描述给你一个字符串 s,找到 s 中最长的 回文子串示例1:输入:s="babad"输出:"bab"解释:"aba"同样是符合题意的答案。示例2:输入:s="cbbd"输出:"bb"提示:1<=s.length<=1000s 仅由数字和英文字母组成解法:classSolution:deflongestPalindrome(sel......
  • LeetCode算法笔记2
    题目描述给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。请你将两个数相加,并以相同形式返回一个表示和的链表。你可以假设除了数字0之外,这两个数都不会以0 开头。示例1:输入:l1=[2,4,3],l......
  • AcWing 2074:倒计数 ← 双指针算法
    【题目来源】https://www.acwing.com/problem/content/2076/【题目描述】艾弗里有一个由N个正整数构成的数组。数组中的第i个整数是Ai。如果一个连续的子数组的长度为m,并且按顺序包含整数m,m−1,m−2,…,2,1,则称它为m倒计数。例如,[3,2,1]是3倒计数。请帮助艾......
  • Leetcode.20 有效括号
    题目描述给定一个只包括'(',')','{','}','[',']' 的字符串s,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。示例输入:s="()"输出:true输入:s="()[]{}"输出:true输入:s=......
  • LeetCode - #96 不同的二叉搜索树(Top 100)
    文章目录前言1.描述2.示例3.答案关于我们前言本题为LeetCode前100高频题我们社区陆续会将顾毅(Netflix增长黑客,《iOS面试之道》作者,ACE职业健身教练。)的Swift算法题题解整理为文字版以方便大家学习与阅读。LeetCode算法到目前我们已经更新到94期,......
  • leetcode刷题笔记
    11妙用数据结构11.2数组448找到所有数组中消失的数字//方法1//1.使用一个数组的下标记录每个对应数字出现的次数//2.遍历数组,根据值为0的元素所在的下标确定没有出现过的数字std::vector<int>findDisappearedNumbers(std::vector<int>&nums){std::vector<in......
  • Leetcode【编辑距离】
    72.编辑距离给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数  。你可以对一个单词进行如下三种操作:插入一个字符删除一个字符替换一个字符示例 1:输入:word1="horse",word2="ros"输出:3解释:horse->rorse(将'h'替换为......