阶乘分解《算法竞赛进阶指南》

$阶乘分解《算法竞赛进阶指南》$
题目地址：197. 阶乘分解 - AcWing题库

题面

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

输入格式

一个整数 $N$。

输出格式

$N!$ 分解质因数后的结果，共若干行，每行一对 $p_i,c_i$，表示含有 $p_i^{c_i}$ 项。按照 $p_i$ 从小到大的顺序输出。

数据范围

$3\le N\le 10^6$

输入样例：

5

输出样例：

2 3
3 1
5 1

样例解释

$5!=120=2^3?3?5$

思路

给定一个整数$n$，然后要求将$n!$进行质因数分解，并且按照算术基本定理的形式输出分解结果中的 $p_i$ 和 $c_i$ 。
算数基本定理：$N=p_1^{c_1}\times p_2^{c_2}\times ...\times p_m^{c_m}$
因此，我们求出小于$n$中有多少个数是质数$x$的倍数，即$n!$中有多少个$x$相乘，也就是$x^{?}$，然后直接输出即可。

标程

vector<PII> p(N);
bool q[N];
int tot;

void primes(int n) {
    for(int i = 2; i <= n; i ++ ) {
        if(!q[i]) p[tot++].fi = i;
        for(int j = 0; p[j].fi <= n / i; j ++ ) {
            q[p[j].fi * i] = 1;
            p[j].se ++;
            if(i % p[j].fi == 0) break;
        }
    }
}

void Solved() {
    int n; cin >> n;
    primes(1e6);
    
    for(int i = 2; i <= n; i ++ ) {
        if(q[i]) continue;
        LL x = i; int res = 0;
        while(x <= n) res += n / x, x *= i;
        cout << i << " " << res << endl;
    }
}