不难发现每个数都不⼤实际没到1e9，这启发我们直接计算对于所有数字，以该数为因数的数字有 多少个即可。按照素数筛法的原理可知，这么做复杂度只有log n
#include<bits/stdc++.h>//因式分解
using namespace std;
const int N=1e6+1;
int n,sum;
int buk[N]={0};//桶（方便后面计数）
int ans[10005]={0};
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
{
int t;
cin>>t;
buk[t]++;
}
for(int i=1;i<N;i++)
{
sum=0;
for(int j=1;i*j<N;j++) sum+=buk[i*j];
ans[sum]=i;//ans[i]=x表示因数有x总共有i个数
}
for(int i=n-1;i>=1;i--) ans[i]=max(ans[i],ans[i+1]);//相当于n~i区间内的数字取大
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}
标签：数字,因式分解,int,buk,ans,变小 From： https://www.cnblogs.com/wjk53233/p/17375451.html