定理:n!中p的倍数为$[n/p]$+$[n/p^2]$+$[n/p^3]$....
所以线性筛之后,分别求出质因子p的个数就可
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int primes[N],cnt;
bool st[N];
int 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]<=n/i;j++){
st[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}
int main(){
cin>>n;
get_primes(n);
for(int i=0;i<cnt;i++){
int p=primes[i];
int s=0,t=n;
while(t){
s+=t/p;
t/=p;
}
cout<<p<<' '<<s<<endl;
}
return 0;
}