算法竞赛进阶指南，138页，阶乘的素因子分解
本题要点： 1、直接套用阶乘的质因数分解公式， n的阶乘中，n! 含有素数p 的因子个数为 [n / p] + [n / p^2] + [n / p^3] + … + [n / p^k] + … 2、先用线性筛法打个素数表， 然后扫描素数表，对于每一个 p <= n 的素数， 执行上面的公式计算素因子的个数。 3、 比较 p^k 和 n的大小关系，使用 long long
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int MaxN = 1000010; int prime[MaxN], v[MaxN]; long long n; int pNum; int fac[MaxN]; long long fac_cnt[MaxN]; void prime_init() //线性筛法求素数 { pNum = 0; for(int i = 2; i <= n; ++i) { if(!v[i]) { v[i] = i, prime[++pNum] = i; } for(int j = 1; j <= pNum; ++j) { if(prime[j] > v[i] || prime[j] > n / i) break; v[i * prime[j]] = prime[j]; } } } void solve() { int m = 0; for(int i = 1; prime[i] <= n && i <= pNum; ++i) { fac[++m] = prime[i]; long long multi = prime[i], count = 0; while(multi <= n) // 这里比较大小，使用 long long 来比较 { count += n / multi; multi *= prime[i]; } fac_cnt[m] = count; } for(int i = 1; i <= m; ++i) { printf("%d %lld\n", fac[i], fac_cnt[i]); } } int main() { scanf("%lld", &n); prime_init(); solve(); return 0; } /* 5 */ /* 2 3 3 1 5 1 */