对于这道题目,其实理解了线性筛法和一个例子就变得格外简单了,这道阶乘分解,非质数不能被输出,所以我们要将质数标记,那这个时候我们就需要用到线性筛质数了,是代码中的函数get_prime(),之后我们要做的就是输出非质数的,但这个数的指数是多少我们怎么得到呢?
我们可以举一个例子来理解一下如何得到阶乘里的某个质数的指数
例如我们要求8的阶乘分解,我们这时要输出2的指数为多少; 1 2 3 4 5 6 7 8
可以看到,有四个数字是2的倍数,也就是:2 4 6 8
之后我们再看4的倍数有多少:4 8
再看八的倍数:8
所以我们最后容易得到2的指数即为4+2+1=7
为什么这样一定能得到其指数呢,其实就相当于每次都让基数(这里是2)乘2,相当于对目标数字除以2,
再举一个例子
比如一开始是2 4 6 8,这时候我们得到了4个2因子
然后我们使得这四个数全都除2
变成了1 2 3 4
这时候还是2的倍数的就剩下两个了,又得到两个2的因子
我们再除以2
变成0 1 1 2
这时候就只有一个2的因子,我们过程中得到的因子全都加起来就得到了最终的答案
了,使得我们能够找到所有数字的2的因数个数
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define int long long
using namespace std;
const int PS = 1e6 + 10;//要筛得的质数范围
int fg[1000010];
int zs[1000010];
void get_prime()
{//欧拉线性筛法
for(int i=2;i<=PS;i++)
{
if(fg[i]==1) continue;
zs[++zs[0]]=i;//是质数,存入,zs[0]的值就是范围内质数的个数
for(int o=2;o*i<=PS;o++) fg[i*o]=1;//标记不是质数的
}
}//目前我见过的最好的一个质数筛板子,一下子就能看明白
void solve()
{
get_prime();
int n;cin>>n;
for(int i=2;i<=n;i++)
{
if(fg[i]==1) continue;
int sum=0;
for(int o=i;o<=n;o*=i)
{
sum=sum+(n/o);
}
if(sum==0) continue;
else cout<<i<<" "<<sum<<endl;
}
}
signed main()
{
IOS;
int T=1;
// cin>>T;
while(T--) solve();
return 0;
}