分解质因数-第12届蓝桥杯国赛Python真题解析

[导读]:超平老师的Scratch蓝桥杯真题解读系列在推出之后,受到了广大老师和家长的好评,非常感谢各位的认可和厚爱。作为回馈,超平老师计划推出《Python蓝桥杯真题解析100讲》,这是解读系列的第61讲。

分解质因数,本题是2021年5月29日举办的第12届蓝桥杯青少组Python编程全国总决赛真题编程部分第2题。题目要求编程计算对于输入的合数N,将其分解质因数后,质因数的个数。

先来看看题目的要求吧。

一.题目说明

提示信息:

质数:是一个大于1的自然数,且除了1和它本身外,不能被其他自然数整除的数。最小的质数是2,1不是质数。

合数:一个正整数,如果除1和它本身以外,还能被其他正整数整除,叫合数。如6是合数,除了1和6以外,还能被2和3整除。

分解质因数:每个合数都可以写成几个质数相乘的形式,其中每个质数都是这个合数的因数,把一个合数用质因数相乘的形式表示出来,叫做分解质因数(分解质因数只针对合数),如合数12 = 2 × 2 × 3。

分解质因数的方法是先用这个合数的最小质因数去除这个合数,结果若是一个质数就不再除下去;若是一个合数就继续按原来的方法从最小质因数除起,直至最后除得的结果是一个质数 。

例如:

合数18分解质因数,首先用最小质因数2去除,除后结果为合数9,继续用最小质因数3去除,除后结果为质数3,就不再除下去。

所以18的质因数为2、3、3,故质因数的个数为3。

图片

编程实现:

给定一个合数N,将N分解质因数后,输出其质因数个数。

输入描述:

输入一个合数N

输出描述:

将N分解质因数后,输出质因数个数

样例输入:

18

样例输出:

3

二.思路分析

这是一道简单的数论题,考查的知识点主要包括循环、条件、除法运算和质数等。

本题涉及的概念比较多,包括因数,质数、合数和质因数,首当其冲的是要分清它们之间的区别。

在小学数学里,两个正整数相乘,那么这两个数都叫做积的因数,或称为约数。

质数和合数是相对的,一个自然数,除了1和本身外,没有其它的因数,就是质数,否则就是合数。

以我们熟悉的数字24为例,如图:

图片

看图说话,这里的2、3、4、6都是24的因数,其中4和6是合数,2和3是质数,所以2和3都属于质因数。

概念清楚了,接下来就是分解质因数的方法和过程了,理解的越透彻,编写代码就越容易。

质因数的分解,最常用的是短除法,步骤如下:

1). 选择最小的质数p = 2,作为除数;

2). 将N除以选定的质数p,如果能整除,则将商作为新的N,同时将p作为一个质因数;

3). 继续使用相同的质数p进行除法操作,如果不能整除,则转到下一步骤;

4). 增加质数p,如果p不能被N整除,那么将p增加1;

5). 重复步骤2、3、4,直到N被完全分解完为止。

什么时候分解完呢,最简单的判断就是n等于1。不过,根据因数的对称特性,可以减少循环次数。

换句话说, 如果整数n有一个大于其平方根的质因子,那么它必然还有一个小于或等于其平方根的质因子(这对质因子相乘得到 n)。因此,我们只需要检查到 p 的平方根即可。

对应的流程图如下:

图片

举个例子,使用短除法对84分解质因数,如图:

图片

解释如下:

1). 开始时,n = 84,将p设置为2;

2). 使用n除以2,即84 / 2,可以整除,找到质因数2,同时将n更新为42;

3). 继续使用n除以2,即42 / 2,可以整除,找到质因数2,同时将n更新为21;

4). 使用n除以2,即21 / 2,不能整除,将p增加1,于是p = 3;

5). 使用n除以3,即21 / 3,可以整除,找到质因数3,同时将n更新为7;

6). 此时p * p = 9,9 > 7,所以循环结束;

7). 最后判断 n 是否大于1,7 > 1,所以7也是质因数。

至此,质因数全部分解完毕,包括2、2、3、7一共4个质因数。

思路有了,接下来,我们就进入具体的编程实现环节。

三.编程实现

根据上面的思路分析,我们编写程序如下:

图片

代码不多,强调3点:

1). 为了方便查看和调试,这里使用factors列表来保存所有的质因数,你也可以直接使用变量统计个数;

2). 进行除法运算时,必须使用整除运算符;

3). 循环结束时,需要判断n是否为1,如果大于1,则它是最后一个质因数,需要加入列表。

至此,整个程序就全部完成了,你也可以输入不同的数字来测试效果啦。

四.总结与思考

本题代码在12行左右,涉及到的知识点包括:

  • 循环语句while;

  • 条件语句;

  • 除法相关运算,包括%和//;

  • 质因数相关的数学知识。

本题难度一般,代码也不多,关键有两点,一是要弄清质因数的相关概念,二是要理解质因数的分解过程。

质数、合数、因数等相关数学知识,一直以来都是在学习编程时研究和讨论最多的话题,必须要熟练掌握,并做到灵活运用。

超平老师给你留一道思考题,在上面的代码中,我们没有判断p是否为质数,怎么就能确保得到的因数一定是质数呢?

你还有什么好的想法和创意吗,也非常欢迎和超平老师分享探讨。

如果你觉得文章对你有帮助,别忘了点赞和转发,予人玫瑰,手有余香😄

需要源码的,可以移步至“超平的编程课”gzh。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

亚信安慧AntDB:解锁数智化的新时代

亚信安慧AntDB的融合实时的特性使得它在数据库领域独树一帜。传统的数据库系统往往只能追求数据的准确性和一致性,但在实际的业务场景中,这些特性并不能满足企业的需求。AntDB的出现打破了传统束缚,为企业带来了全新的数据处理方式&#xff0…

测试用例设计方法-状态迁移图法

一、介绍: 在软件测试领域中,状态迁移图法是一种极为重要且有效的测试方法。状态迁移图法侧重于分析和测试系统中存在的各种状态以及它们之间的迁移关系。所谓状态,就是系统在特定条件下所处的情况或模式,而迁移则是状态之间的转换…

抖音又出王炸级APP,免费的AI写真神器,一键生成不同场景的写真大片(附保姆级教程)

以前想要拍出一组写真大片,是不是还得跑摄像馆,化妆、换装、各种摆 pose、场景布置,少说也要折腾一上午,而且花费还不少。 而现在,有了 AI,在家里,一个人,一部手机,就能…

微同城小程序源码 轻松制作本地生活活动赚钱 带完整的安装代码包以及搭建教程

近年来,本地生活服务市场蓬勃发展,人们对于周边的生活信息、活动资讯等需求日益增长。然而,传统的信息发布方式存在诸多不便,如信息更新不及时、传播范围有限等。微同城小程序源码应运而生。它利用小程序的便捷性和普及性&#xf…

9.为什么有时候会“烫烫烫”——之函数栈桢

目录 1. 什么是函数栈帧 2. 理解函数栈帧能解决什么问题呢? 3. 函数栈帧的创建和销毁解析 3.1 什么是栈? 3.2 认识相关寄存器和汇编指令 3.3 解析函数栈帧的创建和销毁 小知识:烫烫烫~ Q&A 1. 什么是函数栈帧 我们在写C语言代码…

“设置display:block-inline的li或div中添加文字后,导致li或div排版掉落、错位”的原因及解决方法

先说我想实现的效果 然后我就很快的列出来了css .f_wornning{background: url("/assets/images/icon_kaung.png")no-repeat 100% 100%;background-size: 100% 100%;margin: 10px 20px;height: 3rem;line-height: 3rem;color: #d8eebd;.f_wornning_icon{height: 2rem;…

DDoS攻防,本质上是成本博弈!

在互联网里,分布式拒绝服务(DDoS)攻击作为一种常见的网络威胁,持续对网站、在线服务和企业基础设施构成严重挑战。本文旨在探讨实施DDoS攻击的大致成本、以及企业如何采取有效措施来防范此类攻击,确保业务连续性和网络…

【图像增强(空域)】基于直方图增强的图像增强及Matlab仿真

1. 摘要 图像的灰度直方图表示灰度图像中具有每种灰度像素的个数,反映了图像中每种灰度级出现的频率,是图像的基本统计特征之一。直方图均衡方法因为其有效性和简单性已成为图像对比度增强的最常用的方法。其基本思想是根据输入图像的灰度概率分布来确定…

Verilog复习(三)| Verilog语言基础

四种基本的逻辑值 0&#xff1a;逻辑0或“假”1&#xff1a;逻辑1或“真”x&#xff1a;未知z&#xff1a;高阻 三类常量 整型数&#xff1a;简单的十进制格式&#xff0c;基数格式&#xff08;5’O37&#xff0c;4’B1x_01&#xff09; 格式&#xff1a; <size><’b…

微搭低代码入门05文件的上传和下载

目录 1 创建数据源2 创建应用3 创建页面4 设置导航功能5 文件上传6 文件下载总结 小程序中&#xff0c;我们通常会有文件的上传和下载的需&#xff0c;在微搭中&#xff0c;文件是存放在云存储中&#xff0c;每一个文件都会有一个唯一的fileid&#xff0c;我们本篇就介绍如何通…

docker-compose管理jenkins

1.安装docker和compose 1.docker 更新系统&#xff1a;yum update 安装依赖项&#xff1a;yum install -y yum-utils device-mapper-persistent-data lvm2 配置镜像源&#xff1a;yum-config-manager --add-repo http://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce…

js api part5

学生信息管理系统 现在着急没看..........5.15后一定看 没css&#xff1f;c <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta name"viewport" content"widthdevice-width, initial-scal…

桥接模式类图与代码

欲开发一个绘图软件&#xff0c;要求使用不同的绘图程序绘制不同的图形。以绘制直线和圆形为例&#xff0c;对应的绘图程序如表 7.7 所示。 根据绘图软件的扩展性要求&#xff0c;该绘图软件将不断扩充新的图形和新的绘图程序。为了避免出现类爆炸的情况&#xff0c;现采用桥接…

国外大模型使用成本比较

计算每种层级的LLM使用的大致总成本。考虑到每次使用LLM需要3个输入token产生1个输出token的假设&#xff0c;我们可以这样估算总成本&#xff1a; 计算单次使用的token总数&#xff1a; 输入token&#xff1a;3个输出token&#xff1a;1个总计&#xff1a;3输入 1输出 4个to…

服务号转订阅号的操作步骤(吐血整理)

服务号和订阅号有什么区别&#xff1f;服务号转为订阅号有哪些作用&#xff1f;我们知道&#xff0c;公众号分为服务号和订阅号两种&#xff0c;服务号只能企业才可以申请&#xff0c;订阅号是企业和个人都可以申请。其中最大的区别是服务号一个月只能发送4次群发&#xff0c;但…

《金融时报》专刊!量子计算即将迎来新一轮投资浪潮!

内容来源&#xff1a;量子前哨&#xff08;ID&#xff1a;Qforepost&#xff09; 文丨 王珩 浪味仙 排版丨沛贤 深度好文&#xff1a;2000字丨10分钟阅读 编者按&#xff1a;近日&#xff0c;全球著名财经媒体《金融时报》(financial Time)发布专题报道称&#xff0c;澳大利亚…

【Ubuntu永久授权串口设备读取权限‘/dev/ttyUSB0‘】

Ubuntu永久授权串口设备读取权限 1 问题描述2 解决方案2.1 查看ttyUSB0权限&#xff0c;拥有者是root&#xff0c;所属用户组为dialout2.2 查看dialout用户组成员&#xff0c;如图所示&#xff0c;普通用户y不在dialout组中2.3 将普通用户y加入dialout组中2.4 再次查看dialout用…

linux内核网络源码--通知链

内核的很多子系统之间有很强的依赖性&#xff0c;其中一个子系统侦测到或者产生的事件&#xff0c;其他子系统可能都有兴趣&#xff0c;为了实现这种交互需求&#xff0c;linux使用了所谓的通知链。 本章我们将看到 通知链如何声明以及网络代码定义了哪些链 内核子系统如何向通…

水果成篮 ---- 滑动窗口

题目链接 题目&#xff1a; 分析&#xff1a; 题目中&#xff0c; 我们只能连续采摘树&#xff0c; 而且采摘的树不能超过两种&#xff0c;找到可以包含最多树的方案&#xff0c; 所以我们可以理解为&#xff1a; 找到最长的连续子数组&#xff0c; 子数组中的数据种类不大于…

【MySQL数据库】丨一文详解 JdbcTemplate(Spring中的CRUD)

前言 JdbcTemplate 是 Spring框架 中提供的一个对象&#xff0c;用于简化JDBC操作。它使得数据库操作变得更为简单和方便&#xff0c;大大提高了开发效率。 文章目录 前言为何要使用JdbcTemplate在JdbcTemplate中执行SQL语句的方法大致分为3类&#xff1a;案例代码 JdbcTemplat…
最新文章