【C/C++】【基础数论】33、算数基本定理

算术基本定理,又称正整数的唯一分解定理。

说起来比较复杂,但是看一下案例就非常清楚了

任何一个大于 1 的正整数都可以唯一地分解成有限个质数的乘积形式,且这些质数按照从小到大的顺序排列,其指数也是唯一确定的。
例如,整数 60 可以分解为 2×2×3×5,这里的 2、3、5 都是质数,且这种分解方式是唯一的。

质数

如果一个数除了 1 和本身,没有其他的因数,就是质数。

合数

如果一个数除了 1 和本身,还有其他的因数,就是合数。

1  既不是质数,也不是合数。

一点一点过度,别着急,先看一下质数怎么判断

#include <iostream>
using namespace std;int main()
{int n;cin >> n;// 初始化标志变量,默认 n 是质数bool flag = true; for (int i = 2; i <= n; i++){// 如果 n 能被 i 整除if (n % i == 0) {// 将标志变量设为 false,表示 n 不是质数flag = false; // 跳出循环,因为已经确定 n 不是质数了break; }}// 根据标志变量的值输出结果if (flag){cout << n << "是质数。" << endl;}else{cout << n << "不是质数。" << endl;}return 0;
}

初学者是不是都这么写,可能还不屑注释,一堆字母就完事了?

这个写法没毛病,但是执行效率可能不是很高,因为所有的数都要从2到n来除一遍。来看看,稍微升级一点的写法,

#include <iostream>
#include <cmath>
#include <limits>int main() {int n;// 进入一个无限循环,直到输入有效为止while (true) {cout << "请输入一个正整数:";// 尝试读取输入到 n,如果读取成功并且 n 大于 1if (cin >> n && n > 1) {// 跳出循环,输入有效break;} else {// 清除输入流的错误状态标志cin.clear();// 忽略输入流中的剩余字符直到遇到换行符,防止错误输入影响后续输入cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');cout << "输入无效,请重新输入。" << endl;}}bool isPrime = true;// 从 2 开始循环到 n 的平方根(优化后的质数判断范围)for (int i = 2; i <= sqrt(n); i++) {// 如果 n 能被 i 整除if (n % i == 0) {// 将标志变量设为 false,表示 n 不是质数isPrime = false;// 跳出循环,因为已经确定 n 不是质数了break;}}// 根据标志变量的值输出结果if (isPrime) {cout << n << "是质数。" << endl;} else {cout << n << "不是质数。" << endl;}return 0;
}

很多人可能像我一样刚开始学的时候一样,有个疑问。sqrt是干嘛的,为啥这么写。

在这段代码中,sqrt(n)表示对变量n取算术平方根。

  1. sqrt是 C++ 标准库中<cmath>头文件里定义的一个函数,它接受一个参数并返回该参数的算术平方根。
  2. 在这个代码片段中,通过遍历从 2 到sqrt(n)的整数来判断n是否为质数。这样做的目的是优化判断质数的过程。因为如果一个数n不是质数,那么它一定存在一个小于等于sqrt(n)的因子(除了 1 和n本身)。例如,如果n = 100,那么sqrt(100)=10,在判断 100 是否为质数时,只需要检查从 2 到 10 的整数是否能整除 100 即可,而不需要检查到 99,大大减少了循环次数,提高了程序的效率。

可以这么理解,个数如果能被开平方得到一个新的整数,那么这个数一定不是质数

因为能被开平方得到整数意味着该数存在一个相同的因数与其自身相乘得到这个数,比如 9 能被开平方为 3,9 = 3×3,有除了 1 和它本身之外的因数 3,所以不是质数。

比如 41 不能被开平方得到一个整数,41 是质数。

而质数只能被 1 和它自身整除,不存在可以开平方得到但是还是质数的情况的情况。

大大减少了循环次数,提高了程序的效率。

而算术基本定理又称正整数的唯一分解定理,它不完全等同于单纯的分解质因数,但可以通过分解质因数来体现。

算术基本定理指出:任何一个大于 1 的正整数都可以唯一地分解成有限个质数的乘积形式,且这些质数按照从小到大的顺序排列,其指数也是唯一确定的。

举个例子,整数 60 可以分解为,这里的 2、3、5 都是质数,且这种分解方式是唯一的。

而分解质因数只是实现算术基本定理的一种操作手段,算术基本定理强调的是正整数分解为质数乘积的唯一性这一本质属性。

一般我们编程思想和我们数学中用到的短除法非常的类似。简单来说,短除法就是不断地用最小的质因数除以它本身。

给你一个数,你怎么快速分解出他的质因数。就用这个方法。

比如100的质因数是2*2*5*5;那我们利用短除法来求一下。

我们用代码来拆解一下

#include <iostream>
using namespace std;int main()
{// 输入int n;cin >> n;// 输出提示信息cout << n << "的质因数分解为:";// 分解质因数for (int i = 2; i <= n; i++){// 当 n 能被 i 整除时,进入循环while (n % i == 0){// 输出质因数 icout << i << " ";// 将 n 更新为 n 除以 i 的结果n /= i;}}cout << endl;return 0;
}

步骤说明:

  1. 首先从用户处获取一个整数n
    • int n; cin >> n;:定义变量n并读取用户输入的整数。
  2. 输出提示信息,让用户知道即将看到的是输入整数的质因数分解结果。
    • cout << n << "的质因数分解为:";:输出提示语句。
  3. i = 2开始尝试分解质因数,因为 2 是最小的质数。
    • for (int i = 2; i <= n; i++):循环从 2 开始,一直到等于n,确保所有可能的质因数都被考虑到。
  4. n能被i整除时,进入循环,不断输出i并更新n
    • while (n % i == 0):只要n能被i整除,就一直循环。
    • cout << i << " ";:输出找到的质因数i
    • n /= i;:将n更新为n除以i的结果,以便继续寻找下一个质因数。

例如,输入整数 120:

  1. 首先读取输入的 120。
  2. 输出提示信息 “120 的质因数分解为:”。
  3. i = 2开始:
    • 120 能被 2 整除,输出 2,n变为 60。
    • 60 能被 2 整除,再次输出 2,n变为 30。
    • 30 能被 2 整除,又输出 2,n变为 15。
  4. i = 3时:15 能被 3 整除,输出 3,n变为 5。
  5. i = 4不满足循环条件,继续下一个数。
  6. i = 5时:5 能被 5 整除,输出 5,此时n变为 1,循环结束。

最终输出结果为 “120 的质因数分解为:2 2 2 3 5”。

好了,有任何问题我们来评论区讨论一下吧

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/433176.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

mobaxterm、vscode通过跳板机连接服务器

目标服务器&#xff1a;111.111.11.11 跳板机&#xff1a;100.100.10.10 1. mobaxterm通过跳板机连接服务器 1.1 目标服务器信息 1.2 跳板机信息 1.3 登录 点击登录&#xff0c;会输入密码&#xff0c;成功 参考&#xff1a;https://blog.csdn.net/qq_40636486/article/det…

Cocos 3.8.3 实现外描边效果(逃课玩法)

本来想着用Cocos 的Shader Graph照搬Unity的思路来加外描边&#xff0c;发现不行&#xff0c;然后我就想弄两个物体不就行了吗&#xff0c;一个是放大的版本&#xff0c;再放大的版本上加一个材质&#xff0c;这个材质面剔除选择前面的面剔除就行了&#xff0c;果不其然还真行。…

冒泡排序-C语言

1.问题&#xff1a; 从小到大对10个数进行排序&#xff0c;要求使用冒泡排序实现。 2.解答&#xff1a; 排序规律有两种&#xff1a;一种是“升序”&#xff0c;从小到大&#xff1b;另一种是“降序”&#xff0c;从大到小。 3.代码&#xff1a; #include<stdio.h>//头…

展锐平台的手机camera 系统isptool 架构

展锐平台的isptool 主要用于支持展锐各代芯片isp的各效果模块快速tuning和参数生成打包。 具体需要&#xff1a; 一、工具段能在线实时预览到调试sensor经过isp 处理后的图像&#xff0c;也就是各模块的参数在当下实时生效&#xff0c;通过工具能在PC 上在线观看到修改的效果。…

Python中的数据处理与分析:从基础到高级

在数据科学和数据分析领域&#xff0c;Python凭借其丰富的库和强大的生态系统&#xff0c;成为了最受欢迎的语言之一。本文将从基础到高级&#xff0c;详细介绍如何使用Python进行数据处理和分析&#xff0c;涵盖数据清洗、数据转换、数据可视化等多个方面。 1. 数据导入与导出…

【07】纯血鸿蒙HarmonyOS NEXT星河版开发0基础学习笔记-Swiper轮播组件与样式结构重用

序言&#xff1a; 本文详细讲解了关于我们在页面上经常看到的轮播图在鸿蒙开发中如何用Swiper实现&#xff0c;介绍了Swiper的基本用法与属性&#xff0c;及如何面对大段的重复代码进行封装和重用&#xff08;Extend、Styles、Builder&#xff09;&#xff0c;使代码更加简洁易…

WPF项目中使用Caliburn.Micro框架实现日志和主题切换

目录 一、添加Caliburn.Micro框架 二、配置Serilog日志 三、实现主题切换 Caliburn.Micro是MVVM模式的轻量级WPF框架&#xff0c;简化了WPF中的不少用法。这个框架中所有的页面控制都是通过ViewModel去实现的。 以下内容是自己在进行项目实战的同时进行记录的&#xff0c;对于…

局域网广域网,IP地址和端口号,TCP/IP 4层协议,协议的封装和分用

前言 在古老的年代&#xff0c;如果我们要实现两台机器进行数据传输&#xff0c; A员工就得去B员工的办公电脑传数据&#xff08;B休息&#xff0c;等A传完&#xff09;&#xff0c;这样就很浪费时间 所以能不能不去B的工位的同时&#xff0c;还能传数据。这时候网络通信就出来…

智能抠图怎么操作?4款不动手自动抠图的智能神器分享

对于资深的图片设计师们来说&#xff0c;抠图是他们必备的基础技能&#xff0c;没几下功夫就能在PS中操作完成。 然而对于小编这种修图小白来讲&#xff0c;拥有一款傻瓜式智能抠图免费软件&#xff0c;才是硬道理&#xff01; 小到简单的图形文字、大到飞扬细碎的毛发&#…

贴片式TF卡(SD NAND)参考设计

【MK 方德】贴片 TF 卡参考设计 一、电路设计 1、 参考电路&#xff1a; R1~R5 (10K-100 kΩ)是上拉电阻&#xff0c;当 SD NAND 处于高阻抗模式时&#xff0c;保护 CMD 和 DAT 线免受总线浮动。 即使主机使用 SD NAND SD 模式下的 1 位模式&#xff0c;主机也应通过上拉电阻…

传奇微端黑屏不更新地图?传奇微端架设教程——GOM引擎

登录器和网站配置好后&#xff0c;我们进入游戏后会发现是黑屏的&#xff0c;更新不了地图和NPC这些&#xff0c;因为还没有做微端&#xff0c;会黑屏也是正常的。有些老G做了微端但是还是黑屏&#xff0c;就可能是你的微端架设出现了问题&#xff0c;可以参考以下教程。 gom引…

MQTT--快速入门

目录 1、什么是MQTT2、MQTT协议特性3、MQTT协议原理3.1 发布/订阅、主题、会话3.2 MQTT协议中的方法3.3 MQTT协议数据包结构 4、MQTT工作流程总结PS: 1、什么是MQTT MQTT&#xff08;Message Queuing Telemetry Transport&#xff0c;消息队列遥测传输协议&#xff09; &#…

学习之什么是生成器

什么是生成器&#xff08;Generator&#xff09; 1、是一种数据类型能源源不断地生成数据 2、"惰性"特点:一次生成一个值&#xff0c;而不是生成一个序列 3、生成器一定是迭代器比迭代器更简洁使用生成器表达式创建生成器 from typing import Generator, Iterator,…

Excel数据检视——对角线连续数据连线

实例需求&#xff1a;数据表如下图所示&#xff0c;现需要根据规则&#xff0c;在符合要求的单元格上&#xff0c;添加连线。 连续单元格位于对角线方向单元格内容相同连续单元格数量不少于7个 示例代码如下。 Sub LT2RB()Dim objDic As Object, rngData As Range, bFlag As …

fastapp-微信开发GPT项目第一课

0. 开发说明 在学习开发本项目之前&#xff0c;必须保证有以下知识储备和环境工具。 技术栈说明python>3.9、pydantic>2.7.1python基础&#xff0c;http协议fastapi>0.111.0web协程异步框架&#xff0c;有web开发基础&#xff0c;异步编程&#xff0c;类型标注[pyth…

【HTTP】请求“报头”(Host、Content-Length/Content-Type、User-Agent(简称 UA))

Host 表示服务器主机的地址和端口号 URL 里面不是已经有 Host 了吗&#xff0c;为什么还要写一次&#xff1f; 这里的 Host 和 URL 中的 IP 地址、端口什么的&#xff0c;绝大部分情况下是一样的&#xff0c;少数情况下可能不同当前我们经过某个代理进行转发。过程中&#xf…

【Qt | QList 】QList<T> 容器详细介绍和例子代码

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; ⏰发布时间⏰&#xff1a; 2024-09-26 …

国产化低功耗窄带物联网无线通讯方案_ZETA技术

01 物联网系统中为什么要使用ZETA LPWAN 模组 物联网系统中使用ZETA LPWAN模组的原因主要基于以下几个方面&#xff1a; 1、技术优势 低功耗广域网&#xff08;LPWAN&#xff09;特性&#xff1a;ZETA技术是一种基于UNB的低功耗广域网技术协议标准&#xff0c;具有覆盖范围广…

从 Kafka 到 WarpStream: 用 MinIO 简化数据流

虽然 Apache Kafka 长期以来一直是流数据的行业标准&#xff0c;但新的创新替代方案正在重塑生态系统。其中之一是 WarpStream&#xff0c;它最近在 Confluent 的所有权下进入了新的篇章。此次收购进一步增强了 WarpStream 提供高性能、云原生数据流的能力&#xff0c;巩固了其…

【IOS】申请开发者账号(公司)

官网&#xff1a;Apple Developer (简体中文) 申请开发者账号前提 如果是第一次申请建议注册一个新的apple id作为组织的开发者账号。&#xff08;确保apple id的个人信息是真实的&#xff0c;不能是网名或者是其他名。后续的申请步骤需要能和apple id的个人信息对上。&#…