线性筛法
具体做法是在线性筛时预处理出一个 fac 数组来记录这个数的最小质因子, 在分解时就可以递归求解
- inline void sieve() {
- for (int i = 1; i < maxn; ++ i) fac[i] = i;
- for (int i = 2; i < maxn; ++ i) {
- if (fac[i] == i) p[++cnt] = i;
- for (int j = 1; j <= cnt && p[j] * i < maxn; ++ j) {
- if (fac[i * p[j]] = std::min(fac[i * p[j]], p[j]);
- if (i % p[j] == 0) break;
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3269318.html