快速分解质因数

这是普通的线性筛：

bool not_prime[MAXN + 10];
vector <int> prime;void get_prime() {for(int i = 2; i <= MAXN; i++) {if(!not_prime[i]) prime.pb(i);for(int j : prime) {if(1ll * i * j > MAXN) break;not_prime[i * j] = true;if(i % j == 0) break;}}
}

之所以线性筛的复杂度是线性的，是因为每个数只会被它的最小质因子筛掉一次。

这意味着我们可以在某一个数第一次被筛的时候记录它被谁筛了，即记录它的最小质因子：

int minn[MAXN + 10];
vector <int> prime;void get_prime() {for(int i = 2; i <= MAXN; i++) {if(minn[i] == 0) {minn[i] = i;prime.pb(i);}for(int j : prime) {if(1ll * i * j > MAXN) break;minn[i * j] = j;if(i % j == 0) break;}}
}

得到每个数的最小质因子之后就可以快速分解质因数。

具体地，想要分解一个数，只需不断除以它的最小质因子，并记录下质因子被除个数，直到为 \(1\) ：

while(k != 1) {cnt[minn[k]]++;k /= minn[k];
}