题目描述

给定整数 $N$，试把阶乘 $N!$ 分解质因数，按照算术基本定理的形式输出分解结果中的 $pi$ 和 $ci$ 即可

数据范围

$ 1≤ N ≤ 10^6 $

输入样例

5

输出样例

2 3
3 1
5 1

样例解释：$5!= 120 = 2^3 ∗ 3 ∗ 5$

数论(筛素数)

• 先去做AcWing 868. 筛质数这道题
• 首先使用欧拉筛预处理将N范围内的质数打个表；
• 由于n! = 1 * 2 * 3 * ... * n, 暴力的话相当于对1 ~ n所有数都分解质因数然后统计数量，当然这个时间复杂度是 $O(n²sqrt(n))$ 会TLE;
• 而我们实际上只需考虑枚举到质数的情况，由于已经预处理可以$O(1)$判断是否是质数。当枚举到质数的时，将该质数的所有倍数分解质因数，因为质数的倍数肯定包含该质数的因子，只需记录当前这一个质因子的数量，就可以过滤掉大部分的n内的非质数，这个思想来源于埃氏筛。

时间复杂度

• 欧拉筛的时间复杂度是 $O(n)$
• 对质数的所有倍数分解质因子的时间复杂度分析：
  • 由质数定理可知1 ~ n中含有质数的个数是n/lnn,
  • 这块采用了埃氏筛的思想，朴素筛的时间复杂度是$O(nlnn)$, 埃氏筛对其优化了lnn倍, 故时间复杂度是$O(nlnlnn)$
• 故总的时间复杂度是 $ O(nloglogn) $

C++ 代码

#include <iostream>
#include <unordered_map>

using namespace std;
const int N = 1e6 + 10;
bool st[N];
int primes[N];

unordered_map<int, int> dict; // <质数, 数量>

// [预处理]欧拉筛
void get_primes()
{
    int cnt = 0;
    for (int i = 2; i <= N; i ++)
    {
        if (!st[i]) primes[cnt ++] = i;
        for (int j = 0; primes[j] <= N / i; j ++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main(){
    get_primes(); // 欧拉筛

    int n;
    scanf("%d", &n);

    for (int i = 2; i <= n; i ++)
    {
        // 如果是质数, 则把所有质数的倍数都分解质因数
        if (!st[i]){
            for (int j = i; j <= n; j += i)
            {   
                int t = j;
                while(t % i == 0)
                {
                    dict[i] ++;
                    t /= i;
                }
            }

            printf("%d %d\n", i, dict[i]);
        }
    }

    return 0;
}