题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
const int N=1e6+10;
bool st[N];
int cnt,primes[N],sum[N];
void get_primes(int x){
for(int i = 2;i<=x;i++){
if(!st[i])primes[cnt++]=i;
for(int j=0;primes[j]<=x/i;j++)
{
st[primes[j]*i] =true;
if(i%primes[j]==0) break;
}
}
}
int get(int a,int p){
int res = 0;
while(a){
res+=a/p;
a/=p;
}
return res;
}
using namespace std;
int main(){
int n;
cin>>n;
get_primes(n);
for(int i = 0;i<cnt;i++){
int p =primes[i];
sum[i]=get(n,p);
}
for(int i = 0;i<cnt;i++)
cout<<primes[i]<<' '<<sum[i]<<endl;
return 0;
}