质因子分解的基本思路

结构体

struct factor{
    int x, cnt;//x是质因子，cnt是个数
}fac[10];//fac数组开到10就够了

待分解数n的质因子只有两种情况，一个是有一个大于sqrt(n)的质因数，另一种情况是没有大于sqrt(n)的质因数，不可能有2个及以上，因为这样两个数相乘已经大于n了

后面就是把1到sqrt(n)的质数都枚举一遍，看是否可以被整除
全部整除完了以后，再看是否还有质因数，如果有那么这个一定是大于sqrt(n)的质因数
代码如下：

vector<int> prime;
int sqrt_n = (int)sqrt(n * 1.0);
for(int i = 0; prime[i] < sqrt_n; i++){
    if(n % prime[i]){//可以被整除
        fac[num].x = prime[i];
        fac[cnt].cnt = 0;
        while(n % prime[i] == 0){
            fac[num].cnt++;
            n = n / prime[i];//除完以后不需要恢复
        }
        num++;
    }
}
if(n != 1){
    fac[num].x = n;
    fac[num++].cnt = 1;
}