详解与促背模板 -- 算法基础课 -- 数学知识(一):试除法求所有约数
作者:
MW10
,
2025-01-13 22:15:01
,
所有人可见
,
阅读 4
/*
试除法求约数
与质因数不同:
质因数是构成一个数
约数:可以被整除而已,约数之间不是互质的(2,4)
*/
/*
I n :a
对于每个a,顺序输出其所有约数
O 所有约数
I
2
6
8
O
1 2 3 6
1 2 4 8
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> get_divisors(int x)
{
// 求出较小的约数,直接得到另一个
vector<int> res;
for (int i = 1; i <= x / i; i ++ )
if (x % i == 0)
{
res.push_back(i);
// 不同添加两个,相同只添加一个
if (i != x / i) res.push_back(x / i);
}
sort(res.begin(), res.end());
return res;
}
int main()
{
int n;
cin >> n;
while (n -- )
{
int x;
cin >> x;
auto res = get_divisors(x);
for (auto x : res) cout << x << ' ';
cout << endl;
}
return 0;
}