<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

给定整数 $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$

思路1

我们枚举$1\sim n$的所有数，把每一个数的质因子加到一个数组里。
最后输出质因子数量大于$0$的数。

代码1

#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1000010;
int n;
int ans[N];
int main () {
    cin >> n;
    for (int i = 2;i <= n;i++) {
        int t = i;
        for (int j = 2;j <= n / j;j++) {
            while (t % j == 0) {
                ans[j]++;
                t /= j;
            }
        }
        if (t > 1) ans[t]++;
    }
    for (int i = 2;i < N;i++) {
        if (ans[i]) cout << i << ' ' << ans[i] << endl;
    }
    return 0;
}

思路2

T了吧，谁让你复制代码，哈哈哈哈哈
我们一起考虑$n!$的质因子，就是说一次求出$n!$有几个这种质因子。
经过思考，我们可以发现：质因子$x$的数量是$\sum\limits^{i=1}_{x^i\le n}\lfloor\dfrac{n}{x^i}\rfloor$

$1~ ~2~ ~3~ ~ 4~ ~ 5~ ~ 6~ ~ 7~ ~ 8$ 我们求得在$8!$中$2$的个数

$~ ~ ~ ~1~ ~ ~ ~ ~ ~1~ ~ ~ ~ ~ ~ 1~ ~ ~ ~ ~ ~1$ 首先我们先计算出$2$的倍数的个数：$8\div2=4$

$~ ~ ~ ~ ~ ~~ ~ ~ ~ ~ ~ 1 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 1$ 其次我们计算出$4$的倍数的个数：$8\div4=2$

$~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 1$ 最后我们解出8的个数：$8\div8=1$

我们把$4+2+1=7$，所以一共$7$个$2$出现了。

其实就是如果有一个数，他含$x$的最大幂是$x^i$，那么他会在前$i$层都被统计一次。

代码2

#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1000010;
int n;
int primes[N],cnt;
bool is_prime[N];
void get_primes (int n) {
    memset (is_prime,true,sizeof (is_prime));
    is_prime[1] = false;
    for (int i = 2;i <= n;i++) {
        if (is_prime[i]) primes[++cnt] = i;
        for (int j = 1;primes[j] * i <= n;j++) {
            is_prime[primes[j] * i] = false;
            if (i % primes[j] == 0) break;
        }
    }
}
int main () {
    cin >> n;
    get_primes (n);
    for (int i = 2;i <= n;i++) {
        if (!is_prime[i]) continue;
        LL ans = 0;
        for (LL j = i;j <= n;j *= i) ans += n / j;
        if (ans) cout << i << ' ' << ans << endl;
    }
    return 0;
}