开始做法,暴力解题直接1000ms+
算法:质数筛 暴力计数
时间复杂度: 不知道
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef pair<int,int>PII;
const int N=1e6+10;
int n,cnt;
int primes[N];
bool st[N];
unordered_map<int,int> mp; //存质因子对应个数
vector<PII> ans;
void get_primes(){ //质数筛
for(int i=2;i<=N;i++){
if(!st[i]){
primes[++cnt]=i;
}
for(int j=1;primes[j]<N/i;j++){
st[primes[j]*i]=true;
if(i%primes[j]==0)break;
}
}
}
void solve(){
for(int i=2;i<=n;i++){ //枚举阶乘中的每个数
int num=i;
for(int j=1;primes[j]<=num/primes[j];j++){
if(num%primes[j]==0){ //如果可整除
while(num%primes[j]==0){ //计数
mp[primes[j]]++;
num/=primes[j];
}
}
}
if(num>1)mp[num]++; //防止漏网之鱼
}
auto it=mp.begin();
while(it!=mp.end()){ //map遍历将答案存入vector
ans.push_back({it->first,it->second});
it++;
}
sort(ans.begin(),ans.end()); //由pair的第一个数 排序
for(pair t:ans){
printf("%d %d\n",t.first,t.second);
}
}
int main(){
get_primes();
scanf("%d",&n);
solve();
}
Y总做法
其他题解讲的挺好的
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,cnt;
int primes[N];
bool st[N];
void get_primes(){
for(int i=2;i<=n;i++){
if(!st[i]){
primes[++cnt]=i;
}
for(int j=1;primes[j]*i<=n;j++){
st[primes[j]*i]=true;
if(i%primes[j]==0)break;
}
}
}
int main(){
scanf("%d",&n);
get_primes();
for(int i=1;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);
}
}