如何找到一个数的所有质因数,以及如何快速判断一个数是不是质数
前情介绍
今天遇到一个需求:找到一个数所有的质因数。
初步解决
先定义一个判断质数的函数:
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里面直…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...
解读《网络安全法》最新修订,把握网络安全新趋势
《网络安全法》自2017年施行以来,在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂,网络攻击、数据泄露等事件频发,现行法律已难以完全适应新的风险挑战。 2025年3月28日,国家网信办会同相关部门起草了《网络安全…...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...
