质因数分解

acwing的最基础模板 https://www.acwing.com/blog/content/406/
知乎大佬给的各种数据范围模板大全：https://zhuanlan.zhihu.com/p/591377294
对于其中的一部分进行提炼形成自己的模板
1.使用场景：假设有n个数需要分解，每个数最大可能是N,下面给出的这种代码的时间复杂度是\(O(nlogN)\)
思想：通过\(O(n)\)线性筛预处理过程中记录范围内每个数的最小质因数，分解时每个数的最多被计算\(O(logN)\)次。

//预处理：
for (int i = 2; i < N; i++)minp[i] = i;//通过这个初始化省下bool数组空间
int cnt = 0;
for (int i = 2; i < N; i++) {
    if (minp[i] == i) prime[cnt++] = i;
    for (int j = 0; j < cnt && prime[j] * i < N; j++) {
        minp[prime[j] * i] = prime[j];
        if (i % prime[j] == 0) break;
    }
}

//分解阶段
while (num != 1) {
    int p = minp[num];
    
    // work，题目具体逻辑
    
    num /= p;
}