题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
// 对于 5 来说 :
// 质因数2 :
// 5 / 2 = 3 ;
// 还有可能是4造成的
// 5 / 4 = 1 ;
// ans(2) = 2 + 1 = 3 ;
首先分解小于n的所有质数
对于每一个小于n的质数 , 都进行判断即可
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int primes[N],cnt;
bool st[N];
void get_primes(int n){
for(int i=2;i<=n;i++){
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]*i<=n;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 p=primes[i];
int s=0,t=n;
while(t) s+=t/p,t/=p ; // 查找每一个
printf("%d %d\n",p,s);
}
return 0;
}