AcWing 197. 阶乘分解
原题链接
中等
作者:
新
,
2021-05-11 16:20:23
,
所有人可见
,
阅读 237
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=0x3f3f3f3f;
typedef unsigned long long ull;
inline int read(){int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
const int N = 1e6+1000;
const int mod=1e9+7;
const ll in=2147483648;
//const ll maxn=1e15;
const double pi=2.0*asin(1);
ll prime[N];
int v[N];
int tot=0;
void primes(ll n){
memset(v,0,sizeof(v));
for (int i = 2; i <= n; ++i) {
if (v[i]==0)
prime[tot++]=i;
for (int j = 0; j < tot; ++j) {
if (i*prime[j]>n) break;
v[i*prime[j]]=1;
if (i%prime[j]==0) break;
}
}
}
ll qpow(ll a,ll b){
ll res=1;
while (b){
if (b&1) res*=a;
a*=a;
b>>=1;
}
return res;
}
int main()
{
int n=read();
primes(n);
for (int i = 2; i <= n; ++i) {
if (v[i]==0)
{
ll ans=0;
printf("%d ",i);
for (int j = 1;qpow(i,j)<=n ; ++j) {
ans=ans+n/qpow(i,j);
}
printf("%lld\n",ans);
}
}
}