有效地获取给定数字的所有除数

Question

根据这个帖子，我们可以通过下面的代码得到一个数的所有约数。

for (int i = 1; i <= num; ++i){
    if (num % i == 0)
        cout << i << endl;
}

例如，数字24的除数是1 2 3 4 6 8 12 24。

在搜索了一些相关的帖子后，我没有找到任何好的解决方案。有什么有效的方法来实现这一点吗？

我的解决方案：

1. 通过这个解求出给定数的所有素因子
2. 得到这些基本因子的所有可能组合

然而，这似乎不是一个好办法。

Answer 1

到目前为止，在科学上还没有已知的算法复杂性（具有多项式复杂性的算法）的有效方法。所以像已经建议的那样迭代到平方根是最好的。

主要是因为这一点，目前使用的大部分加密算法都基于这样的假设，即计算任何给定整数的素因式分解都非常耗时。

Answer 2

你真的应该检查到num的平方根为sqrt(num) * sqrt(num) = num:

这些线上的东西：

int square_root = (int) sqrt(num) + 1;
for (int i = 1; i < square_root; i++) { 
    if (num % i == 0&&i*i!=num)
        cout << i << num/i << endl;
    if (num % i == 0&&i*i==num)
        cout << i << '\n';
}

Answer 3

因素是成对的。<代码> 1 和<代码> 24 ，<代码> 2 和<代码> 12 ，<代码> 3 和<代码> 8 ，<代码> 4 和<代码> 6 。

您的算法的改进可能是迭代到num的平方根，而不是一直到num，然后使用num/i计算配对因子。