题目描述
给定整数 N ,试把阶乘 N! 分解质因数,按照算术基本定理的形式输出分解结果中的 pi 和 ci 即可。
输入格式
一个整数N。
输出格式
N! 分解质因数后的结果,共若干行,每行一对pi,ci,表示含有pcii项。按照pi从小到大的顺序输出。
数据范围
1≤N≤10^6
样例
输入样例:
5
输出样例:
2 3
3 1
5 1
这道题的思路很容易想到,先用埃筛把1e6的素数筛出来(欧拉筛也可以,不过这道题1e6的复杂度埃筛不会炸),然后用O(n)把所有的n以内的素数都扫一遍,而次数就是ans=n/(ai^1)+n/(ai^2)+……+n/(a[i]^p),(a[i]^p<=n,a[i]^(p+1)>n),边扫边输出即可。
复杂度大概是(nlogn)(应该会更多,不好计算)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000000;
bool s[MAXN+10];
long long n;
void Aya()
{
s[1]=0;s[0]=0;
for(int i=2;i<=MAXN;++i)
if(s[i])
for(int j=i+i;j<=MAXN;j+=i)
s[j]=0;
return;
}
int main()
{ memset(s,1,sizeof(s));
Aya();
cin>>n;
for(int i=0;i<MAXN;++i)
{
if(i>n)
break;
if(s[i])
{
long long ans=0;
for(long long j=i;j<=n;j*=i)
ans+=(n/j);
cout<<i<<' '<<ans<<endl;
}
}
return 0;
}