题目描述
试除法求约数
C++ 代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> get_divide(int x)
{
vector<int> res;
for(int i=1;i<=x/i;i++) //时间复杂度为O(sqrt(n))
{
if(x%i==0)
{
res.push_back(i);
if(i!=x/i)res.push_back(x/i); //当成对出现的另一个约数与当前约数不同时才能加入到res中
}
}
sort(res.begin(),res.end());
return res;
}
int main()
{
int n;
cin>>n;
while(n--)
{
int x;
cin>>x;
auto res=get_divide(x);
for(auto t:res) cout<<t<<" "; //依次输出res中的元素
cout<<endl;
}
return 0;
}