Acwing.197.阶乘分解(题解)xiaodangao

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

输入格式

一个整数N。

输出格式

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

数据范围

$1 \le N \le 10^6$

输入样例：

输出样例：

2 3
3 1
5 1

样例解释

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

水题，分解质因数，然后看到一个不一样的做法，是真的惊艳到我了，或许以后能够借鉴他的思路，换个角度思考问题。
思路，先用筛子筛出 $10^6$ 内的素数，然后考虑 $n$ 这个数，对于每个素数 $x$ 而言， $n$ 是 $x$ 的 $n/x$ 倍，也就是说，对于小于等于 $x$ 的数，形如 $x,2x,3x...kx$ 这种形式有 $\lfloor \frac{n}{x} \rfloor$ 个，那么很容易的得到，对于 $x$ 而言，有 $\lfloor \frac{n}{x} \rfloor$ 个数是 $x$ 的倍数，即能被 $x$ 整除；然后我们将 $x*x$ 与上面的含义一样，意为计算 $n$ 有几个 $x*x$ 的倍数，这一步操作我们将 $n/x$ ，含义一样。
$Code:$

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n,prime[N],tot;
bool st[N];
void init(){
    for(int i=2;i<=N;++i){
        if(!st[i]){
            prime[++tot] = i;
            if(i>=10000)continue;
            for(int j=i*i;j<=N;j+=i)st[j] = true;
        }
    }
}
int main(){
    init();
    scanf("%d",&n);
    for(int i=1;prime[i]<=n;++i){
        int now = n,ans = 0;
        while(now){
            ans+=(now/prime[i]);
            now/=prime[i];
        }
        printf("%d %d\n",prime[i],ans);
    }
    return 0;
    
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。