AcWing 197. 阶乘分解
原题链接
中等
作者:
最后五分钟
,
2024-04-05 03:11:19
,
所有人可见
,
阅读 4
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define de(x) cout<<#x<<" = "<<x<<" "
#define deg(x) cout<<#x<<" = "<<x<<endl
using namespace std;
const int N=1e6+10;
typedef pair<int,int> PII;
int p[N],cnt;
int st[N],sd[N];
void getp(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i])p[cnt++]=i;
for(int j=0;i*p[j]<=n;j++)
{
st[i*p[j]]=1;
if(i%p[j]==0)break;
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
getp(n);
for(int i=0;i<cnt;i++)
{
int x=p[i],res=0,j=1;
while(x<=n)res+=n/x,x*=p[i];
if(res)cout<<p[i]<<" "<<res<<endl;
}
return 0;
}