本文共 1213 字，大约阅读时间需要 4 分钟。

一.题目链接：

二.题目大意：

给一个整数 N （N ≤ 1e6）

求 N！的质因数及其个数.

三.分析：

直接暴力是 O(N sqrt(N))，肯定不行.

不过可以先把 N 以内的质因数打表，再统计 1 ~ N 中每个质数出现的个数.

对于当前质数 prime[i] 来说

1 ~ N 中共出现了 N/prime[i] 次 prime[i]的倍数.

1 ~ N 中共出现了 N/prime[i]/prime[i] 次 prime[i] * prime[i] 的倍数.

...

这样便可在 O(N + logN * logN) 完成.

四.代码实现：

#include 
   
    using namespace std;typedef long long ll;const int M = (int)1e6;const int inf = 0x3f3f3f3f;int tot;int prime[M + 5];bool is_prime[M + 5];map 
    
      mp;void get_prime(){    memset(is_prime, 1, sizeof(is_prime));    is_prime[0] = is_prime[1] = 0;    for(int i = 2; i <= M; ++i)    {        if(is_prime[i])            prime[++tot] = i;        for(int j = 1; j <= tot && i * prime[j] <= M; ++j)        {            is_prime[i * prime[j]] = 0;            if(i % prime[j] == 0)                break;        }    }}int main(){    get_prime();    int n;    scanf("%d", &n);    for(int i = 1; i <= tot && prime[i] <= n; ++i)    {        int cnt = 0;        ll num = prime[i];        while(num <= n)        {            cnt += n / num;            num *= prime[i];        }        mp[prime[i]] = cnt;    }    for(auto iter = mp.begin(); iter != mp.end(); ++iter)        printf("%d %d\n", iter->first, iter->second);    return 0;}