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); } }AcWing - 197 - 阶乘分解
标签：
原文地址：https://www.cnblogs.com/Inko/p/11528776.html