https://www.acwing.com/problem/content/199/
求解n!的质因数分解，n数量级1e6。
一个最简单的思路就是暴力分解每个数的质因数，复杂度过高。
换一种思路，当需要批量处理的时候，用线性筛求出每个数的最小质因数，然后对这个数进行质因数分解只需要log级别。
191ms：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e6;
int minp[MAXN + 5];
int p[MAXN + 5], ptop;
void sieve(int n) {
minp[1] = 1;
for(int i = 2; i <= n; i++) {
if(!p[i]) {
p[++ptop] = i;
minp[i] = i;
}
for(int j = 1, t; j <= ptop && (t = i * p[j]) <= n; j++) {
p[t] = 1;
minp[t] = p[j];
if(i % p[j])
;
else
break;
}
}
}
int cnt[MAXN + 5];
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
int n;
scanf("%d", &n);
sieve(n);
for(int i = 2; i <= n; ++i) {
int tmp = i;
while(tmp > 1) {
++cnt[minp[tmp]];
tmp /= minp[tmp];
}
}
for(int i = 2; i <= n; ++i) {
if(cnt[i])
printf("%d %d\n", i, cnt[i]);
}
}还有另一种思路复杂度是一样的，但是不需要这么多除法。显然n以内拥有因子p的恰好有n/p个，而拥有两个因子p的恰好有n/(p^2)个，用乘法直接计算理论上更快。
43ms：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e6;
int p[MAXN + 5], ptop;
void sieve(int n) {
for(int i = 2; i <= n; i++) {
if(!p[i]) {
p[++ptop] = i;
}
for(int j = 1, t; j <= ptop && (t = i * p[j]) <= n; j++) {
p[t] = 1;
if(i % p[j])
;
else
break;
}
}
}
int cnt[MAXN + 5];
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
int n;
scanf("%d", &n);
sieve(n);
for(int i = 1; i <= ptop; ++i) {
int ans = 0;
for(ll j = p[i]; j <= n; j *= p[i])
ans += n / j;
printf("%d %d\n", p[i], ans);
}
}