阶乘分解_(质因数分解)

原题链接：197. 阶乘分解 - AcWing题库

题意：求阶乘的算术基本定理

思路

数值较大的质因数分解用质因数分解模板不一定时间够用

可以先枚举质数，对每个质数遍历，求解每个质数的倍数，质数幂次的倍数，然后加和作为算术基本定理中的指数大小

这种方法局限在数可以拆为多个数字相乘，可以转化为求各个数中质数的倍数的问题

实现

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <map>
 
using namespace std;
 
typedef long long LL;
 
const int N = 1000010;
 
LL n;
LL primes[N];
int cnt;
bool st[N];
 
 
void get_primes(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; primes[j] * i <= n; j ++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}
 
 
int main()
{
    cin >> n;
    
    get_primes(n);
    
    for(int j = 0; j < cnt; j ++)
    {
        int p = primes[j];
        int t = n / p;
        
        int s = 0;
        while(t) s += t, t /= p;
        
        cout << p << ' ' << s << endl;
    }
    
    return 0;
}