当前位置: 首页 > 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…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...

Linux中《基础IO》详细介绍

目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改&#xff0c;实现简单cat命令 输出信息到显示器&#xff0c;你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...

算法打卡第18天

从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7…...