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

2021-12-17 00:00:00 algorithm math c++ factorization

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

According to this post, we can get all divisors of a number through the following codes.

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

例如24的除数是1 2 3 4 6 8 12 24.

搜索了一些相关的帖子，没有找到好的解决办法.有什么有效的方法可以做到这一点吗?

After searching some related posts, I did not find any good solutions. Is there any efficient way to accomplish this?

我的解决方案:

  1. 通过这个解决方案.
  2. 获取这些质因数的所有可能组合.

然而，这似乎不是一个好方法.

However, it doesn't seem to be a good one.

推荐答案

因素是成对的.1 and 24, 2 and 12, 3 and 8、4 和 6.

Factors are paired. 1 and 24, 2 and 12, 3 and 8, 4 and 6.

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

An improvement of your algorithm could be to iterate to the square root of num instead of all the way to num, and then calculate the paired factors using num / i.

相关文章