当前位置: 首页 > news >正文

02 分解质因子

一、数n的质因子分解

题目描述:

输入一个数n(n<=10^6),将数n分解质因数,并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入 5 

输出 5 1

输入 10

输出 2 1 5 1

朴素解法:

首先求出1~n的所有质数,每个质数每个质数的进行去除,要保证n中除尽除完,直到把n除到1为止。

程序实现:

#include<bits/stdc++.h>using namespace std;const int N=1e6;int prime[N],idx;
bool st[N];void init(){for(int i=2;i<N;i++){if(!st[i]) prime[++idx]=i;for(int j=1;prime[j]*i<N;j++){st[prime[j]*i]=1;if(i%prime[j]==0) break;}}
}
int main(){init();int n;cin>>n;if(!st[n]) cout<<n<<" "<<1<<endl;else{for(int i=1;prime[i]<=n&&i<=idx;i++){int p=prime[i];int sum=0;while(n%p==0){sum++;n/=p;}if(sum) cout<<p<<" "<<sum<<endl;}}return 0;
}

优化思路:

其一:n如果除掉了前面的某个质因子,后面不能再被某个质因子的倍数整除了,证明比较简单,使用反证法就可以。

其二:n中最多只含有一个大于\sqrt{n}的因子。证明通过反证法:如果有两个大于sqrt(n)的因子,那么相乘会大于n,矛盾。证毕

基于上面的两条结论,只要从1~\sqrt{n}把每个数都除一遍,除尽除完,最后剩下的数如果不为1,这个数就是最大的质因子

代码实现

#include<bits/stdc++.h>
using namespace std;int main(){int n;cin>>n;for(int i=2;i<=n/i;i++){int sum=0;while(n%i==0){sum++;n/=i;}if(sum) cout<<i<<" "<<sum<<endl;}if(n!=1) cout<<n<<" "<<1<<endl;return 0;
}

二、阶乘的质因子分解

题目描述

题目分析:

我们枚举1∼n的所有数,把每一个数的质因子加到一个数组里。
最后输出质因子数量大于0的数。 时间复杂度为O(n^2/ln n)

程序实现:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int prime[N],idx;
bool st[N];void init(){for(int i=2;i<N;i++){if(!st[i]) prime[++idx]=i;for(int j=1;prime[j]*i<N;j++){st[prime[j]*i]=1;if(i%prime[j]==0) break;}}
}
int ans[N];  //ans[i]表示第i个质因子的个数
int main(){init();int n;cin>>n;for(int i=2;i<=n;i++){  //枚举每一个数for(int j=1;prime[j]<=i&&j<=idx;j++){int p=prime[j];int cur=i;while(cur%p==0){ans[j]++;cur/=p;}}}for(int i=1;i<=idx;i++){if(ans[i]) cout<<prime[i]<<" "<<ans[i]<<endl;}return 0;
}

优化思路:

我们不去枚举每个数,而是枚举每个质因子,看下在2~n中每个质因子出现的次数

在1x2x3x4x5x6x......x n-1 x n其中

能够被2整除的数有:

1*2 2*2 3*2....... i*2  其中2*i<=n        个数 i=n/2

能够被{2}^{2}整除的数有:

1*{2}^{2} 2*{2}^{2} 3*{2}^{2}......i*{2}^{2} 其中i*{2}^{2}<=n  个数i=n/{2}^{2}

...........

在统计被2整除的个数时,相当于把每个数都除了2,剩下的数还有可能被2整除那些数是{2}^{2}的数,{2}^{2}的数有n/{2}^{2}个,剩下的数还有可能被2整除,那些数是{2}^{3}的数,{2}^{3}的数有n/{2}^{3}个,............所以2作为因子的个数为

\frac{n}{2}+\frac{n}{​{2}^{2}}+\frac{n}{​{2}^{3}}.........+\frac{n}{​{2}^{p}}   其中{2}^{p}<=n

同理3作为因子的个数为:

\frac{n}{3}+\frac{n}{​{3}^{2}}+\frac{n}{​{3}^{3}}.........+\frac{n}{​{3}^{p}}   其中{3}^{p}<=n

等等

所以只要枚举每个质数,使用循环在求出该质数作为因子的个数即可,每个质数求解时,

p=\log_{2}{n},质数的个数为\frac{n}{\ln n},因此总的时间复杂度为\log_{2}{n}*\frac{n}{\ln n}=\frac{\ln{n}}{\ln{2}}*\frac{n}{\ln n}=\frac{n}{\ln{2}} ,即时间复杂度为O(n)

相关文章:

02 分解质因子

一、数n的质因子分解 题目描述&#xff1a; 输入一个数n&#xff08;n<10^6&#xff09;,将数n分解质因数&#xff0c;并按照质因数从小到大的顺序输出每个质因数的底数和指数。 输入 5 输出 5 1 输入 10 输出 2 1 5 1 朴素解法&#xff1a; 首先求出1~n的所有质数…...

科技赋能智慧水利——山海鲸软件水利方案解析

作为山海鲸可视化软件的开发者&#xff0c;我们深感荣幸能为我国智慧水利建设提供强大助力。作为钻研数字孪生领域的开创者&#xff0c;我们希望不仅能为大家带来免费好用&#xff0c;人人都能用起来的数字孪生产品&#xff0c;还希望以其独特的技术优势和创新设计理念&#xf…...

C4.5决策树的基本建模流程

C4.5决策树的基本建模流程 作为ID3算法的升级版&#xff0c;C4.5在三个方面对ID3进行了优化&#xff1a; &#xff08;1&#xff09;它引入了信息值&#xff08;information value&#xff09;的概念来修正信息熵的计算结果&#xff0c;以抑制ID3更偏向于选择具有更多分类水平…...

本科毕业设计过程中应该锻炼的能力 (深度学习方向)

摘要: 本文以本科毕业设计做深度学习方向, 特别是全波形反演为例, 描述学生应在此过程中锻炼的能力. 搭建环境的能力. 包括 Python, PyTorch 等环境的安装.采集数据的能力. 包括 OpenFWI 等数据集.查阅资料的能力. 包括自己主要参考的文献, 以及其它相关文献 (不少于 20 篇). …...

深度学习——pycharm远程连接

目录 远程环境配置本地环境配置&#xff08;注意看假设&#xff01;&#xff01;!这是很多博客里没写的&#xff09;步骤1步骤2步骤2.1 配置Connection步骤2.2 配置Mappings 步骤3 配置本地项目的远程解释器技巧1 pycharm中远程终端连接技巧2 远程目录技巧3 上传代码文件技巧4 …...

信号量机制解决经典同步互斥问题

生产者 / 消费者问题、读者 / 写者问题和哲学家问题是操作系统的三大经典同步互斥问题。本文将介绍这三个问题的基本特点以及如何用信号量机制进行解决。 在分析这三个问题之前&#xff0c;我们首先需要了解用信号量机制解决同步互斥问题的一般规律&#xff1a; 实现同步与互斥…...

java基础09-==和equals()的区别,附代码举例

和equals()的区别 在Java中&#xff0c;和equals()是两个不同的运算符&#xff0c;它们在比较对象时有着本质的区别。 运算符: 用于比较两个基本数据类型&#xff08;如int、char等&#xff09;或两个对象的引用。 当用于比较基本数据类型时&#xff0c;它会比较它们的值。 当…...

qml与C++的交互

qml端使用C对象类型、qml端调用C函数/c端调用qml端函数、qml端发信号-连接C端槽函数、C端发信号-连接qml端函数等。 代码资源下载&#xff1a; https://download.csdn.net/download/TianYanRen111/88779433 若无法下载&#xff0c;直接拷贝以下代码测试即可。 main.cpp #incl…...

LabVIEW电路板插件焊点自动检测系统

LabVIEW电路板插件焊点自动检测系统 介绍了电路板插件焊点的自动检测装置设计。项目的核心是使用LabVIEW软件&#xff0c;开发出一个能够自动检测电路板上桥接、虚焊、漏焊和多锡等焊点缺陷的系统。 系统包括成像单元、机械传动单元和软件处理单元。首先&#xff0c;利用工业相…...

第十一站:多态练习ODU

实现动态切换 ODU.h #pragma once #include <iostream> using namespace std; #define ODU_TYPE_311_FLAG "311" #define ODU_TYPE_335_FLAG "335" enum class ODU_TYPE {ODU_TYPE_311,ODU_TYPE_335,ODU_TYPE_UNKNOW };class ODU{ public:ODU();//发…...

【深度学习】详解利用Matlab和Python中 LSTM 网络实现序列分类

🔗 运行环境:Matlab、Python 🚩 撰写作者:左手の明天 🥇 精选专栏:《python》 🔥 推荐专栏:《算法研究》 🔐#### 防伪水印——左手の明天 ####🔐 💗 大家好🤗🤗🤗,我是左手の明天!好久不见💗 💗今天分享Matlab深度学习—— LSTM 网络实现序列分...

Unity 工厂方法模式(实例详解)

文章目录 在Unity中&#xff0c;工厂方法模式是一种创建对象的常用设计模式&#xff0c;它提供了一个接口用于创建对象&#xff0c;而具体的产品类是由子类决定的。这样可以将对象的创建过程与使用过程解耦&#xff0c;使得代码更加灵活和可扩展。 工厂模式的主要优点如下&…...

2024年美赛数学建模思路 - 案例:异常检测

文章目录 赛题思路一、简介 -- 关于异常检测异常检测监督学习 二、异常检测算法2. 箱线图分析3. 基于距离/密度4. 基于划分思想 建模资料 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 一、简介 – 关于异常…...

一键完成,批量转换HTML为PDF格式的方法,提升办公效率

在当今数字化的时代&#xff0c;HTML和PDF已经成为两种最常用的文件格式。HTML用于网页内容的展示&#xff0c;而PDF则以其高度的可读性和不依赖于平台的特性&#xff0c;成为文档分享和传播的首选格式。然而&#xff0c;在办公环境中&#xff0c;我们经常需要在这两种格式之间…...

【重点问题】攻击面发现及管理

Q1&#xff1a;在使用长亭云图极速版时&#xff0c;是否需要增设白名单扫描节点&#xff1f; 长亭云图极速版高级网络安全产品基于一种理念&#xff0c;即攻击面发现是一个不断变换且需要持续对抗的过程。在理想的情况下&#xff0c;用户应当在所有预置防护设施发挥作用的环境…...

UE4外包团队:国外使用UE4虚幻引擎制作的十个知名游戏

​ 1.俄罗斯方块效果&#xff08;任天堂 Switch、PlayStation 4、PC、Xbox&#xff09; 2.耀西的手工世界&#xff08;任天堂 Switch&#xff09; 3. Final Fantasy 7 Remake Intergrade (PlayStation, PC) 4.《堡垒之夜》&#xff08;PC、Nintendo Switch、PlayStation、Xb…...

解决springboot+mybatisplus返回时间格式带T

原因&#xff1a;我service实现类的代码是 Overridepublic Map<String, Object> queryDictPage(Map<String, Object> queryMap) {Map<String,Object> map new HashMap<>();QueryWrapper<Dict> wrapper new QueryWrapper<>(); // …...

纯命令行在Ubuntu中安装qemu的ubuntu虚拟机,成功备忘

信息总体还算完整&#xff0c;有个别软件更新了名字&#xff0c;所以在这备忘一下 1. 验证kvm是否支持 ________________________________________________________________ $ grep vmx /proc/cpuinfo __________________________________________________________________…...

Vue的学习Day1_是什么以及两种风格

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、Vue是什么&#xff1f;二、渐进式框架1.渐进式 三、Vue API风格1.选项式 API (Options API)2.组合式 API (Composition API) 四、Vue 开发前的准备 前言 放…...

磁悬浮人工心脏的不良事件分析:美国FDA数据库的启示

引言&#xff1a; 左心室辅助装置&#xff08;LVAD&#xff09;是治疗末期难治性心力衰竭&#xff08;HF&#xff09;患者的有效手段。磁悬浮人工心脏HeartMate-3&#xff08;磁悬浮人工心脏&#xff09;作为第三代LVAD&#xff0c;自2017年获得美国食品药品监督管理局&#x…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...