题意
把阶乘 n! 分解质因数,按照算术基本定理的形式输出分解结果中的 pi 和 ci
思路
1:先找出分解后可能会出现的质因数(pi),即用欧拉筛筛出 1~n 中的所有质数,它们都有出现的可能
2:对应每个 pi,求出它的 ci ,ci = n / pi + n / (pi^2) + …直到 pi 的次方大于 n
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n,cnt;
bool st[N];
int primes[N];
void get_primes(){
for(int i=2;i<=n;i++){
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++){
st[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}
int main(){
cin>>n;
get_primes(); // 欧拉筛
for(int j=0;j<cnt;j++){
int p=primes[j];
int t=n,s=0;
while(t) s+=t/p,t/=p; // 核心代码
cout<<p<<" "<<s<<endl;
}
return 0;
}