如何根据X的质因数分解高效获取X在范围内的所有因子？

Question

我有一些算法（在网上很容易找到）可以用来找质因数和约数，但我不知道怎么把它们扩展到在一个范围内找这些约数。比如说，找100的所有约数，范围在23到49之间（这个范围是随便定的）。我还希望这个方法能高效一些，这样可以处理更大的数字和更大的范围。一开始我想用一个和范围一样大的数组，然后用所有小于等于上限的质数来筛选这个数组里的元素，最终得到约数的列表，但对于大的范围来说，这样会占用太多内存。

有没有简单的方法可以直接生成约数呢？

Answer 1

如果你知道一个数字 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

一旦你得到了所有的约数列表，你就可以从中挑选出在你需要的范围内的那些。

Answer 2

当Malvolio在（间接地）讨论这个问题时，我个人觉得如果你想在一个范围内找因子，素因数分解可能用不上。我会从一个数字的平方根开始，比如说int t = (int)(sqrt(n))，然后逐渐减小这个数字，直到
1. t是一个因子
2. 一直减到1，或者t/n的范围已经到达了（设置一个标志），然后（两者）都已经超出了这个范围。

或者如果你的范围比较小，可以直接检查那些值本身。

Answer 3

设 n[i] 是你要考虑的数字 x 的第 i 个因子，并且 i 小于 m。对于任何一个整数 j，它的值大于 1 且小于 2^m，那么所有 n[j[r]] 的乘积，其中 j[r] 是 j 的第 r 位，都是 x 的一个因子。

举个例子，考虑数字 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 有点争议）。