质因子分解的问题就是给定一个 n 使得 n 能够分解为多个因子的乘积形式，并且相同因子用指数形式表示；
例如 180=22_32_5;
对于这个问题，很好理解，我们的目的就是寻找其因子，通常的方法也就是从 0 开始枚举，然后通过取模或者整除操作来看是否是我们需要的元素；
具体的思路如下所示：
我们首先建立一个结构体：
struct factor{int xint cnt}fac\[10\]
这里为每一个符合条件的因子创立一个结构体，fac 数组是当前该数字所有因子存储数组；
结构体内 x 代表当前的因子，cnt 代表当前因子出现的个数；
这里开 10 的目的是如果开更大会导致 int 溢出，并没有什么必要；
接下来就是计算部分；
我们对 1~sqrt(n) 挨个进行枚举；这里借鉴了寻找判定素数的概念，因为如果 k 存在，为 n 的质因子，对于 n/k*n 来说，其也是 n 的质因子，我们的目的是寻找最小质因子，所以只需要枚举到 sqrt(n) 就可以；
接下来要注意理解一个质因子分布的问题；
对于我们枚举到 sqrt(n)，必然会出现两种情况：
- 所有质因子都在 sqrt(n) 的枚举范围内；
- 有一个质因子大于 sqrt(n)，但其余的说有质因子都在 sqrt(n) 范围内，并且该较大的质因子必为素数；
我们该怎么理解这个问题，第一条很好理解，显然成立，那么第二条必然成立吗？
会不会有两个数字斗大于 sqrt(n)，并且这两个既可能是合数有可能是素数？
首先，不可能有两个质因子大于 sqr(n)，这样会导致乘积大于 n，所以不符合初始条件；
那么剩下的质因子一定为素数嘛？
如果这个质因子是合数，则说明可以分解，必定可以分为多个较小质因子的乘积，或者多个数和一个素数的乘积；
所以无论那种情况，都是两种情况中的一个；
所以接下来我们通过枚举，对一个质因子猛除，记录他的出现次数，如果有余数，进行下一个数字的枚举猛除；直到到达 sqrt(n) 边界，如果还是有余数，则说明有第二个条件发生，有个较大的质因子，所以直接记录，因为这个质因子只可能出现一次，如果多次会使得乘积大于 n；
大致的判断逻辑如下所示：
for(int i\=0;i<sqrt(n);i++){
if(n%prime\[i\]==0){
fac\[num\].x\=prime\[i\];
fac\[num\].cnt\=0;
while(n%prime\[i\]==0){
fac\[num\].cnt++;
n/=prime\[i\];
}
num++;
}
}
if(n!=1){
fac\[num\].x\=n;
fac\[num++\].cnt\=1;
}
若有收获，就点个赞吧
0 人点赞
