分解质因数

[导读]：超平老师的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。