题目链接
题目描述
给定整数 \(N\),试把阶乘 \(N!\) 分解质因数,按照算术基本定理的形式输出分解结果中的 \(p_i\) 和 \(c_i\) 即可。
输入格式
一个整数 \(N\)。
输出格式
\(N!\) 分解质因数后的结果,共若干行,每行一对 \(p_i,c_i\),表示含有 \({p_i}^{c_i}\) 项。按照 \(p_i\) 从小到大的顺序输出。
数据范围
\(1≤N≤10^6\)
输入样例:
5
输出样例:
2 3
3 1
5 1
样例解释
\(5!=120=23∗3∗5\)
解题思路
\(n!\) 中质因数 \(p\) 的个数至少有 \(\frac{n}{p}\) 个,\(p^2\) 的个数至少有 \(\frac{n}{p^2}\)个,\(\dots\)
其中,\(p^2\) 中质因子的个数在 \(p\) 中也算过一次,累加即可~
故 \(n!\) 中质因子的个数:
- 时间复杂度:\(O(nlogn)\)
代码
#include<cstdio>
using namespace std;
int prime[1000000];
int v[1000005];
int m,n;
void primes(int n)
{
for(int i=2;i<=n;i++)
{
if(!v[i])
{
v[i]=i;
prime[++m]=i;
}
for(int j=1;j<=m;j++)
{
if(v[i]<prime[j]||i*prime[j]>n)break;
v[i*prime[j]]=prime[j];
}
}
}
int main()
{
scanf("%d",&n);
primes(n);
for(int i=1;i<=m;i++)
{
int p=prime[i],c=0,t=n;
while(t>=p)c+=t/p,t/=p;
printf("%d %d\n",p,c);
}
return 0;
}