给定整数 N,试把阶乘 N! 分解质因数,按照算术基本定理的形式输出分解结果中的 pi 和 ci 即可。
输入格式
一个整数 N。
输出格式
N! 分解质因数后的结果,共若干行,每行一对 pi,ci,表示含有 pi^ci 项。按照 pi 从小到大的顺序输出。
数据范围
3≤N≤10^6
输入样例:
5
输出样例:
2 3
3 1
5 1
样例解释
5!=120=2^3∗3∗5
题意:
任给一个整数n
,让我们将n!
分解质因数。将每个质因子及其对应的次数求出。(n<=1e6
)
本题思路:(两步骤)
时间复杂度分析:O(n)
1~n
*有n/logn
个素数,每一个质数p
求取一下它对应的次数,我们按照下面的方法求:
每一个质数算次数都需要 log{p,n}
次,算出来总运算次数是:
log{2,n} + log{3,n} + log{5,n} + ...
(每一项都是以质数为底的对数,根据公式一共有n / log{2,n}
项)
我们放缩一下,上式 <= n / log{2,n} * log{2,n} = n
(n / log{2,n}
表示1~n
中质数的个数),
我们最后再加上线筛预处理的O(n)
,因此这个算法时间复杂度最终是 O(n) 的,总次数大概在2e6
,属于合法范围内。
两份代码:一份while,一份for
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int primes[N],cnt;
bool st[N];
void init(int n)
{
for(int i=2;i<=n;++i)
{
if(!st[i]) primes[cnt++] = i;
for(int j=0;primes[j]*i<=n;++j)
{
st[primes[j]*i] = true;
if(i%primes[j]==0) break;
}
}
}
int main()
{
int n;
cin>>n;
init(n);
for(int i=0;i<cnt;++i)
{
int t = n;
int p = primes[i];
int s = 0;
while(t>=1) s += t/p, t /= p;
cout<<primes[i]<<' '<<s<<endl;
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int primes[N],cnt;
bool st[N];
void init(int n)
{
for(int i=2;i<=n;++i)
{
if(!st[i]) primes[cnt++] = i;
for(int j=0;primes[j]*i<=n;++j)
{
st[primes[j]*i] = true;
if(i%primes[j]==0) break;
}
}
}
int main()
{
int n;
cin>>n;
init(n);
for(int i=0;i<cnt;++i)
{
int p = primes[i];
int s = 0;
for(int j=n; j>=1; j/=p) s+=j/p;
cout<<primes[i]<<' '<<s<<endl;
}
return 0;
}