题目描述
给定整数 N,试把阶乘 N! 分解质因数,按照算术基本定理的形式输出分解结果中的 pi 和 ci 即可。
样例
输入:
5
输出:
2 3
3 1
5 1
算法1
此题不能先乘起来,不然会是爆炸级别的了,很直白的方式就是把阶层(nx(n-1)x(n-2)x(n-3)这种)里面的每一个数的质因子都求出来,然后质因子的次数相加就能得到最后的结果,但是这是正着做的,我们直接反着做。可以先把素数prims[i]筛出来,对每一个素数,对于n来说求素数prims[i]的次数,对于这个数C*P的s次方来说,在p等于一次方的时候筛一次,p二次方的时候筛一次………p的s次方筛一次。所以它会被筛c次。
时间复杂度 O(n)
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=1000010;
int prims[N],cnt,n,m;
bool st[N];
void init(int n){
for(int i=2;i<=n;i++){
if(!st[i]) prims[cnt++]=i;
for(int j=0;prims[j]*i<=n;j++){
st[i*prims[j]]=true;
if(i%prims[j]==0) break;
}
}
}
int main(){
cin>>n;
init(n);
for(int i=0;i<cnt;i++){
int p=prims[i];
int s=0;
for(int j=n;j;j/=p) s+=j/p;
cout<<p<<' '<<s<<endl;
}
return 0;
}