摘要: 基本信息 即是一个数的约数，并且是质数，比方8=2×2×2，2即是8的质因数。12=2×2×3，2和3即是12的质因数。把一个式子以12=2×2×3的方式表明，叫做分化质因数。16=2×2×2×2,2即是16的质因数，把一个合数写成几个质数相乘的方式表明，这也...
基本信息
即是一个数的约数，并且是质数，比方8=2×2×2，2即是8的质因数。12=2×2×3，2和3即是12的质因数。把一个式子以12=2×2×3的方式表明，叫做分化质因数。16=2×2×2×2,2即是16的质因数，把一个合数写成几个质数相乘的方式表明，这也是分化质因数。
分化质因数的办法是先用一个合数的最小质因数去掉这个合数，得出的数如果一个质数，就写成这个合数相乘方式；如果一个合数就持续按原来的办法，直至终究是一个质数 。
分化质因数的有两种表明办法，除了大家最常用知道的“短除分化法”之外，还有一种办法即是“塔形分化法”。
分化质因数对处理一些自然数和乘积的疑问有很大的协助，一起又为求最大公约数和最小公倍数做了主要的铺垫。
Pollard Rho因数分化
1975年，John M. Pollard提出了第二种因数分化的办法，Pollard Rho迅速因数分化。该算法时间复杂度为O（n^(1/4)）。
计算方法
短除法
求最大公因数的一种办法，也可用来求最小公倍数。
求几个数最大公因数的办法，开始时用调查比较的办法，即：先把每个数的因数找出来，然后再找出公因数，终究在公因数中找出最大公因数。
例如：求12与18的最大公因数。
12的因数有：1、2、3、4、6、12 、16、18。
18的因数有：1、2、3、6、9、18、24。
12与18的公因数有：1、2、3、6。
12与18的最大公因数是6。
这种办法对求两个以上数的最大公因数，特别是数目较大的数，显然是不便利的。于是又选用了给每个数别离分化质因数的办法。
12=2×2×3
18=2×3×3
12与18都能够分红几种方式不一样的乘积，但分红质因数连乘积就只有以上一种，并且不能再分化了。所分出的质因数无疑都能整除原数，因而这些质因数也都是原数的约数。从分化的成果看，12与18都有公约数2和3，而它们的乘积2×3=6，即是 12与18的最大公约数。
选用分化质因数的办法，也是选用短除的方式，只不过是别离短除，然后再找公约数和最大公约数。如果把这两个数合在一起短除，则更简单找出公约数和最大公约数。
从短除中不难看出，12与18都有公约数2和3，它们的乘积2×3=6即是12与18的最大公约数。与前边别离分化质因数相比较，能够发现：不仅成果相同，并且短除法竖式左边即是这两个数的公共质因数，而两个数的最大公约数，即是这两个数的公共质因数的连乘积。
实践使用中，是把需求核算的两个或多个数放置在一起，进行短除。
在核算多个数的最小公倍数时，对其间恣意两个数存在的约数都要算出，其它无此约数的数则原样落下。终究把一切约数和终究剩余无法约分的数连乘即得到最小公倍数。
只富含1个质因数的数一定是亏数。
