思路

我们普通求阶乘的时候,边乘边除质数,就可以保证不爆范围。

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=1e6+7;

//int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
int is_pri[N],pri[N],ans[N],cnt=0;
void init(){
	for(int i=2;i<N;i++){
		if(!is_pri[i]) pri[++cnt]=i;
		for(int j=1;j<=cnt&&pri[j]*i<N;j++){
			is_pri[i*pri[j]]=1;
			if(i%pri[j]==0) break;
		}
	}
}

signed main(){
	int n,res,tmp;
	init();
	cin>>n;
	res=1;
//	for(int i=1;i<=cnt;i++) cout<<pri[i]<<" ";
	for(int i=1;i<=n;i++){
		res*=i;
		tmp=sqrt(res);
		for(int j=1;j<=cnt&&pri[j]<tmp;j++){
			while(res%pri[j]==0){
				res/=pri[j];
				ans[pri[j]]++;
			}
		}
		if(res<N&&!is_pri[res]){
			ans[res]++;
			res=1;
		}
	}
	for(int i=2;i<N;i++){
		if(ans[i]) cout<<i<<" "<<ans[i]<<"\n";
	}
	return 0;
}