对一个数进行质因子分解的朴素做法是O(sqrt(n))的试除法
如果可以预处理出mindiv[i]数组，即每个数的最小质因子，则进行因式分解时，可以对数n，不断执行n/=mindiv[n]，即可分解。
例题：https://ac.nowcoder.com/acm/contest/45670/E
题解：https://www.bilibili.com/video/BV1NP411c7TM/?p=4&spm_id_from=pageDriver&vd_source=75ae018f8d1181302d7ea76b60c928f4
模板：可以在埃氏筛法中直接记录：
int primes[N];
bool not_prime[N];
int cnt = 0;
void get_primes(int n)
{
for (int i = 2; i < n; i++)
{
if (!not_prime[i])
{
min_div[i]=i;
primes[cnt++] = i;
for (LL j = LL(i)*i; j <= n; j += i)
{not_prime[j] = true;min_div[j]=i;}
}
}
}
View Code
原理：这种写法的埃氏筛法只会筛一次
标签：埃氏,因数分解,int,复杂度,primes,预处理,log From： https://www.cnblogs.com/ydUESTC/p/16890597.html