https://ac.nowcoder.com/acm/problem/51043——(阶乘分解)

题目：https://ac.nowcoder.com/acm/problem/51043
思路：先将n以内的质数进行打表，然后计算每一个质数的贡献次数。
代码：

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<utility>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1e6+5;
const LL mod=1e9+7;
int read() {
    char ch=getchar();int x=0,f=1;
    while(ch<'0' || ch>'9')    {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int gcd_(int a,int b) {return b==0?a:gcd_(b,a%b);}
LL fpow(LL a,LL b) {
    LL res=1;
    while(b) {
        if(b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
int p[maxn];
int pr[maxn];
int cnt=0;
void init(int n) {
    for(int i=2;i<=n;++i) {
        if(!p[i]) pr[cnt++]=i;
        for(int j=0;j<cnt;++j) {
            if(i*pr[j]>n) break;
            p[i*pr[j]]=1;
            if(i%pr[j]==0) break;
        }
    }
}
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
//    cout<<"Accepted!\n";
    int n;
    cin>>n;
    init(n);
    for(int i=0;i<cnt;++i) {
        LL res=0;
        for(LL j=pr[i];j<=n;j*=1LL*pr[i]) res+=1LL*n/j;
        cout<<pr[i]<<" "<<res<<"\n";
    }
    return 0;
}