c++ - 如果我有 X 的素数分解，如何有效地获得 X 的所有除数？

Question

所以我有用于素数分解和除数获取的算法（很容易在网上搜索），但我不知道如何扩展它以在一个范围内找到这些除数。例如 23 到 49 之间的 100 的所有除数（任意）。但也有一些有效的东西，所以我可以将它扩展到更大范围内的大数字。起初我在考虑使用一个范围大小的数组，然后使用所有素数 <= 上限来筛选该数组中的所有元素以返回一个最终的除数列表，但对于大范围，这也是内存密集型。

有没有一种简单的方法可以直接生成除数？

Answer 1

让n[i]成为你的数字的第 i 个x因子i< m。j对于任何大于 1 且小于的整数，所有的位2^m的乘积是的除数。n[j[r]]j[r]r-thjx

考虑 105。它的因数是[3, 5, 7]。所以 3 因子，2^3 是 8：

 0  000                = 1
 1  001              7 = 7
 2  010          5     = 5
 3  011          5 * 7 = 35
 4  100      3         = 3
 5  101      3   *   7 = 21
 6  110      3 * 5     = 15
 7  111      3 * 5 * 7 = 105

看？105 的所有可能除数（0 和 7 有点可疑）。

Answer 2

由于 Malvolio 正在（间接）进行，如果你想在一个范围内找到因子，我个人不会发现素数分解的用途，我会从 int t = (int)(sqrt(n)) 开始，然后递减直到
1. t 是一个因素
2. 完整的 util t 或 t/n 范围已达到（一个标志），然后（两者）已离开该范围

或者，如果您的范围相对较小，请检查这些值本身。

Answer 3

如果您知道n的因数，则可以通过取n的因数的幂集的乘积来计算n的除数——包括 1 和n在内的那些数，它们均分n：

function divisors(n)
    divs := [1]
    for fact in factors(n)
        temp := []
        for div in divs
            if fact * div not in divs
                append fact * div to temp
        divs := divs + temp
    return divs

获得完整的除数列表后，您可以仅选择所需范围内的除数。