对$n!$进行质因数分解的一种高效算法
首先,筛出$<=n$的素数
蓝后,对$n$反复除以$prime$,同时$cnt+=n/prime$
$n!$中含有该$prime$的个数即为$cnt$
#include<iostream>
#include<cstdio>
#include<cstring>
#define re register
using namespace std;
#define N 10002
int n,v[N],pri[N],cct;
int main(){
scanf("%d",&n);
for(re int i=;i<=n;++i){
if(!v[i]) v[i]=pri[++cct]=i;
for(re int j=;j<=cct;++j){
if(pri[j]>i||pri[j]*i>n) break;
v[pri[j]*i]=pri[j];
}
}
for(re int i=;i<=cct;++i){
int cnt=;
for(re int j=n;j;j/=pri[i]) cnt+=j/pri[i];
printf("%d %d\n",pri[i],cnt);
}return ;
}