AcWing 197. 阶乘分解
原题链接
中等
作者:
半个完美主义
,
2024-04-28 16:07:23
,
所有人可见
,
阅读 4
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6 + 5;
int primes[N];
bool st[N];
int cnt;
void get_primes(int n){
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(){
int n; cin >> n;
get_primes(n);
for(int i = 0; i < cnt; i++){
int xx = n;
int sum = 0;
while(xx){
sum += xx / primes[i];
xx /= primes[i];
}
cout << primes[i] << " " << sum << endl;
}
}