一个通常情况足够快，且好写的求约数算法
算法描述
首先求质因数，复杂度为 sqrt(最大质因数) 将原数分解为多个质因数的乘积后，求约数的方法也很简单。 每各个不同 的质因数，将该质因数的不同次方和不含该质因子的已知约数相乘，合并到结果集中。
如分求 36 的约数，首先分解为 2 × 2 × 3 × 3
- 初始化，集合中仅有 [1] 一个约数
此时结果集为[1] - 将 2 和 4 分别和 [1] 相乘 得到 [2, 4], 合并
此时结果集为[1, 2, 4] - 将 3 和 9 分别和 [1, 2, 4] 相乘 得到 [3, 6, 12, 9, 18, 36] 合并
此时结果集为[1, 2, 4, 3, 6, 12, 9, 18, 36]
实现
分解质因数和后面的过程可以合并执行，不需要记录质因子，最终代码如下
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
vector<int> get_divisor(int x) { vector<int> ans(1, 1); for (int d = 2; d * d <= x; d++) { if (x % d) { continue; } size_t pos = ans.size(); int pow_d = 1; while (x % d == 0) { x /= d; pow_d *= d; for (size_t i = 0; i < pos; i++) { ans.push_back(ans[i] * pow_d); } } } size_t pos = ans.size(); if (x != 1) { for (size_t i = 0; i < pos; i++) { ans.push_back(ans[i] * x); } } return ans; } |
原创文章，转载请注明： 转载自Comzyh的博客
本文链接地址: 快速求约数(divisor)