如何找到一个数的所有质因数,以及如何快速判断一个数是不是质数
前情介绍
今天遇到一个需求:找到一个数所有的质因数。
初步解决
先定义一个判断质数的函数:
def is_Prime(number):i = 2count = 0while i < number:if number % i == 0 :count += 1i += 1if count > 0:return Falseelse:return True
接着定义一个寻找质因数的函数:
def find_Prime_Factor(number):i = 2while i < number + 1:if(number % i == 0):if is_Prime(i):print(i , end=" ")i += 1
ok ,搞定了
进一步分析
这个程序可以是可以,但是至少有两处可以改进的地方:
首先,判断质数要遍历到number,也就是时间复杂度为O(n),通过改变while循环的条件可以把遍历数目变为number/2,时间复杂度记为O(n/2)【其实时间复杂度还是O(n)】:
while i < number // 2 + 1:
然后,记得之前有一个方法是遍历到平方根就可以了,这个时候只需要遍历到,这个时候和上面的相比就有本质的区别了,时间复杂度为O(
):
while (i < int(math.sqrt(number)) + 1):
在这里需要说明的两点:
1、必须要把平方根取整
2、后面的“ + 1 ”必须有
最后,质数判断基本已经到了最极限的水平了,当然可能还有更好的,笔者没学习到,如果有大佬,欢迎补充。
那就是求因数需要优化了,这个时候参考上面求质数的过程,我们是否也可以通过这几方面来求呢?答案是肯定的,在此附上快速求一个数所有因数的代码:
def find_factors(num):factors = []for i in range(1, int(num ** 0.5) + 1):if num % i == 0:factors.append(i)if num // i != i:factors.append(num // i)factors.sort()return factors
整合到找质因数的函数也比较容易:
def find_Prime_Factor(number):i = 2# while i < number + 1:while i < int(number ** 0.5) + 1:if(number % i == 0):if is_Prime(i):print(i, end=" ")if num // i != i:if is_Prime(num // i):print(num // i , end=" ")i += 1
完结撒花
可以看出,这个相对来说很基础,之所以记录下来是因为对【后面的“ + 1 ”必须有】的思考,为什么需要 + 1 呢?其实很简单,不加就会把平方根下的这个因数给遗漏掉,导致把一个🈴数误判为质数,这是不允许的。
相关文章:
如何找到一个数的所有质因数,以及如何快速判断一个数是不是质数
前情介绍 今天遇到一个需求:找到一个数所有的质因数。 初步解决 先定义一个判断质数的函数: def is_Prime(number):i 2count 0while i < number:if number % i 0 :count 1i 1if count > 0:return Falseelse:return True 接着定义一个寻找质…...
西瓜书之神经网络
一,神经元模型 所谓神经网络, 目前用得最广泛的一个定义是“神经网络是由具有适应性的简单单元组成的广泛并行互连的网络,它的组织能够模拟生物神经系统对真实世界物体所做出的交互反应”。 M-P神经元 M-P神经元:接收n个输入(…...
C++进阶 特殊类的设计
本篇博客介绍:介绍几种特殊的类 特殊类的设计 设计一个类不能被拷贝设计一个类 只能在堆上创建对象设计一个类 只能在栈上创造对象设计一个类不能被继承单例模式饿汉模式懒汉模式单例模式对象的释放问题 总结 设计一个类不能被拷贝 我们的拷贝只会发生在两个场景当…...
NLP序列标注问题,样本不均衡怎么解决?
【学而不思则罔,思而不学则殆】 1.问题 NLP序列标注问题,样本不均衡怎么解决? 2.解释 以命名实体识别(NER)为例,这个样本不均衡有两种解释: (1)实体间类别数量不均衡…...
大端和小端
大端和小端 大端(Big Endian)和小端(Little Endian)是两种不同的字节序排列方式,用于解释多字节数据在内存中的存储顺序。 在大端字节序中,高位字节(最高有效位)存储在低位地址&am…...
C++快速回顾(二)
前言 在Android音视频开发中,网上知识点过于零碎,自学起来难度非常大,不过音视频大牛Jhuster提出了《Android 音视频从入门到提高 - 任务列表》,结合我自己的工作学习经历,我准备写一个音视频系列blog。C/C是音视频必…...
【LVS】1、LVS负载均衡群集
1.群集的含义: Cluster、群集、集群 由多台主机构成并作为一个整体,只提供一个访问入口(域名与IP地址);可伸缩 2.集群使用的场景: 高并发 3.企业群集的分类: 根据群集所针对的目标差异&a…...
el-tree 懒加载树
el-tree 懒加载树 添加自定义图标指定叶子节点懒加载 <template><div><el-treeclass"filter-tree":data"treeData":props"defaultProps"ref"tree"lazy:load"loadTree":expand-on-click-node"true"…...
到江西赣州ibm维修服务器之旅-联想X3850 x6黄灯故障
2023年08月15日,一位江西赣州工厂客户通过朋友介绍与冠峰售前工程师取得联系,双方对产品故障前后原因沟通的大致情况如下: 服务器型号:Lenovo system x3850 x6 为用户公司erp仓库服务器 服务器故障:正常使用过程中业…...
VMware 虚拟机三种网络模式详解
文章目录 前言桥接模式(Bridged)桥接模式特点: 仅主机模式 (Host-only)仅主机模式 (Host-only)特点: NAT网络地址转换模式(NAT)网络地址转换模式(NAT 模式)特点: 前言 很多同学在初次接触虚拟机的时候对 VMware 产品的三种网络模式不是很理解,本文就 VMware 的三种网络模式进行…...
ASP.NET指定变量数据类型,速度提高了100倍
ASP.NET指定变量数据类型,速度提高了100倍由自动编程人工智能 发表在专区 10亿次求余数为0的计算: ASP运行速度130秒左右 ASP.NET Dim i, c, max 如果不指定数据类型,运行要120秒左右 Dim i, c, max As Integer 指定数据类型,运…...
PyArmor 一键加密
使用: pyarmor obfuscate main.py 参考:Python代码加密方案_python加密代码_wgr_1009的博客-CSDN博客 一 简介 PyArmor是用于保护Python代码的工具,它可以将Python脚本编译成加密的字节码,以增加代码的保护性。它的主要目的是防…...
redis--持久化
redis持久化 在 Redis 中,持久化是一种将数据从内存写入到磁盘的机制,以便在服务器重启或崩溃时能够恢复数据。Redis 提供了两种主要的持久化方式:RDB(Redis Database Snapshot)和AOF(Append-Only File&am…...
管理外部表
官方文档地址:Managing Tables 关于外部表 Oracle 数据库允许您对外部表中的数据进行只读访问。外部表定义为不驻留在数据库中的表,通过向数据库提供描述外部表的元数据,数据库能够公开外部表中的数据,就好像它是驻留在常规数据…...
数字图像处理-AWB跳变
1、自动白平衡(AWB)算法是相机中常用的图像处理技术,它能够自动调整图像中的白平衡,使得图像中的颜色更加真实、自然。然而,在实际应用中,AWB算法也存在着一些问题,例如AWB跳变(Whit…...
DNNGP、DeepGS 和 DLGWAS模型构成对比
一、DNNGP DNNGP 是基于深度卷积神经网络,这个结构包括一个输入层,三个卷积层,一个批标准化层,两个dropout层,一个平坦化层,一个 dense层。 dropout层:在神经网络中,dropout层是一个非常有效的正…...
postgresSQL 配置文件设置
postgres.conf 是 PostgreSQL 数据库的主要配置文件,其中包含了许多关于数据库行为的设置。以下是一些常见的配置项: listen_addresses: 这个参数定义了 PostgreSQL 服务监听的网络地址。默认值是 ‘localhost’,这意味着只有本机的客户端才能…...
【bug】Unity无法创建项目
bug UnityHub无法创建项目 UnityHub无法创建项目 出现的问题:在创建新项目时弹出来一个 无法创建项目 尝试的方法: 刷新许可证 ❌没用退出账号重新登陆 ❌没用重启电脑 ❌没用 最后发现是什么问题呢? 2021.3.3这个版本我之前在资源管理器中…...
跨境外贸业务,选择动态IP还是静态IP?
在跨境业务中,代理IP是一个关键工具。它们提供了匿名的盾牌,有助于克服网络服务器针对数据提取设置的限制。无论你是需要经营管理跨境电商店铺、社交平台广告投放,还是独立站SEO优化,代理IP都可以让你的业务程度更加丝滑ÿ…...
Hlang社区-社区导航栏实现
文章目录 前言项目结构导航实现创作中心移动小球消息提示完整代码前言 okey,这里的话是我们社区导航栏的实现: 废话不多说,看看效果: 我甚至为此用New Bing生成了一个Logo。 项目结构 废话不多说,先来看到我们的项目结构: 在这里导航栏是一个组件。 在App.vue里面直…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...
AI语音助手的Python实现
引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...
数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !
我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...
