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;
}

关于线性筛，知道了一年，说说我的理解.
对于break条件：我们举例子为了让每个数只被自己的minp筛掉，30只能在i=15,prime[j]=2的时候被标记。
而在这之前会经历i=10,但由于10%2==0，30不会被i=10,prime[j]=3的时候筛掉，因为prime[j]=2的时候f循环就会break
关于原理证明：
我们还是举例子来理解：
比如i=91,我们可以用它能标记912，913…..916,917.
以273为例，91不能整除3且当前还在循环中说明3是913的minp.
1.因为从小到大枚举的所有质数,所以当”i%primes[j]!=0”时,primes[j]一定小于i的最小质因子,
primes[j]一定是primes[j]i的最小质因子.
2.因为是从小到大枚举的所有质数,所以当”i%primes[j]==0”时,primes[j]一定是i的最小质因子,
而primes[j]又是primes[j]的最小质因子,因此primes[j]是iprimes[j]的最小质因子.