首页 > 其他分享 >如何高效寻找素数

如何高效寻找素数

时间:2024-03-04 20:23:13浏览次数:36  
标签:__ count 高效 return int 寻找 素数 range

目录

题目

  • 输入n,返回[2,n)中素数的个数

暴力

  • 从2开始到n,一个一个判断是不是素数,是的话就计数器加1。判断素数函数:从2开始到n,判断有没有是n的倍数,有倍数就不是素数
def countPrimes(n:int):
    count=0
    for i in range(2,n):
        if (isPrimes(i)):
            count+=1
    return count
def isPrimes(n:int):
    for i in range(2,n):
        if n%i==0:#如果这个数从2开始到自己都没有一个是倍数,则是素数
            return False
    return True
if __name__ == "__main__":
    n=int(input())
    print(countPrimes(n))
  • 时间复杂度o(n^2)

优化

  • 判断素数函数中for循环范围改变了,因为:比如n=12,我们只需要判断26,不需要判断62,中间是以根号n分开的,所以我们判断素数时,只需要判断[2,根号n)
import math
def countPrimes(n:int):
    count=0
    for i in range(2,n):
        if (isPrimes1(i)):
            count+=1
    return count
def isPrimes1(n:int):
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:#如果这个数从2开始到自己都没有一个是倍数,则是素数
            return False
    return True
if __name__ == "__main__":
    n=int(input())
    print(countPrimes(n))
  • 时间复杂度o(sqrt(n))

埃拉托斯特尼素数筛选法

  • 先初始化数组全为True,然后把是素数的倍数全部删去,最后统计数组中是True的个数返回
import math
def countPrimes1(n: int) -> int:
    isPrime = [True for i in range(n)]  # 初始化数组为全 True,表示所有数都是质数
    for i in range(2, int(math.sqrt(n)) + 1):#乘法因子的对称性
        if isPrime[i]:#是素数的情况下,把他的倍数全部删去
            for j in range(i*i, n, i):#从i*i开始,到n以i为步长,都是i的倍数,全置为False
                isPrime[j] = False
    count = 0
    for i in range(2, n):
        if isPrime[i]:#统计isPrime数组中是ture的个数
            count += 1
    return count
if __name__ == "__main__":
    n=int(input())
    print(countPrimes1(n))
  • 时间复杂度o(NloglogN)

标签:__,count,高效,return,int,寻找,素数,range
From: https://www.cnblogs.com/lushuang55/p/18052582

相关文章

  • Java编程的利器:Pair和Triple无缝解决多值返回问题,助力编写高效代码
    在实际编码中,经常会遇到一个方法需要返回多个值的情况,你编写一个方法,需要同时返回某个操作的结果和一些相关的附加信息。使用传统的方式,你可能需要创建一个包含这些信息的自定义类或者使用集合(如Map)来存储这些值。然而,这往往使得代码变得臃肿,而且对于调用方来说,理解和提取这些值......
  • 【转】[java] 第一百个素数输出
    publicclassHundredthPrime{publicstaticvoidmain(String[]args){intcount=0;for(inti=2;;i++){for(intj=2;j<=i;j++){if(i%j==0){if(i>j)......
  • 在github开源市场如何高效寻找优秀开源项目
    作为程序员,不论是开发还是学习,肯定会用到开源项目,那么怎么快速在开源网站找到这些项目呢?常用的开源网站有:github和giteegithub是全球最大的开源社区,今天就以github为例,演示一下github界面一般来说,优秀的项目,维护会比较频繁,提交数也就会多一点。当然,一个好的项目,它......
  • 掌握C语言指针,轻松解锁代码高效性与灵活性(中)
    ✨✨欢迎大家来到贝蒂大讲堂✨✨......
  • 10个技巧,3分钟教会你github高效寻找开源项目
    大家好,我是知微!作为程序员,不论是开发还是学习,肯定会用到开源项目,那么怎么快速在开源网站找到这些项目呢?常用的开源网站有:github和giteegithub是全球最大的开源社区,今天就以github为例,演示一下github界面一般来说,优秀的项目,维护会比较频繁,提交数也就会多一点。当......
  • 买卖股票的最佳时机——差值的最值的遍历寻找
    题目描述:给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。(1)只能选择某一天买入这只股票,并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算所能获取的最大利润。返回可以从这笔交易中获取的最大利润。如果不能获取任何利润......
  • CloudCanal x Hive 构建高效的实时数仓
    简述CloudCanal最近对于全周期数据流动进行了初步探索,打通了Hive目标端的实时同步,为实时数仓的构建提供了支持,这篇文章简要做下分享。基于临时表的增量合并方式基于HDFS文件写入方式临时表统一Schema任务级的临时表基于临时表的增量合并方式Hive目标端写入方式和......
  • 一位有着近 10 年 iOS 开发经验的全职爸爸如何高效管理时间?
    名字:Mindr开发者/团队:FlorianVates平台:iOS,iPadOS,Android正在开发中请简要介绍下这款产品有没有发现自己总是不断推迟待办事项的通知?Mindr以一种全新的方法来解决这个问题,它直观的界面设计将待办事项的进度直接显示在桌面上,就像查看Apple的电池小组件一样,......
  • C#GDI高效绘图(转载)
    汇总利用双缓冲技术在C#中实现GDI高效绘图 双缓冲是将图片在显示到DC前,现在要内存建一个DC,也就是用于存储这张图片的内存区,然后在将这部分update到你要显示的地方这样,可以防止画面抖动很大这样和你说吧,如果要实现你要的效果,你必须用指针访问内存比如,把程序声明成unsaf......
  • 高效的PDF文字提取技术
    无论是行政法规、学术论文还是企业合同,PDF文档为我们提供了一种便捷、稳定的信息传递方式。然而,从PDF文件中提取文本信息对于数据分析、内容编辑等后续处理来说至关重要。PDF文本提取技术是一种可以从各类PDF文档中准确抽取文字的技术手段。无论是书籍、报告、信件,该技术都能够通......