这种找到给定数字的最小因子的方法如何工作？

Question

我最近遇到了一种方法，它 returns 给定数字的最小因数：

public static int findFactor(int n) 
{
    int i = 1;

    int j = n - 1;

    int p = j; // invariant: p = i * j

    while(p != n && i < j) 
    {
        i++; 
        p += j;

        while(p > n) 
        {
            j--; 
            p -= i;
        }
    }

    return p == n ? i : n;
}

检查该方法后，我已经能够（很可能是错误的）确定其中一些变量分别代表的数量：

n = the int that is subject to factorization for 
    the purposes of determining its smallest factor

i = the next potential factor of n to be tested

j = the smallest integer which i can be multiplied by to yield a value >= n

问题是我不知道 p 代表什么数量。内部循环似乎将 (p+=j) - n 视为 i 的潜在倍数，但考虑到我认为 j 代表的内容，我不明白这怎么可能是真的对于所有 i，或者外循环如何解释执行的内循环的 "extra" 迭代在后者因 p < n

而终止之前

假设我已经正确确定了n、i和j代表什么，那么p代表什么数量？

如果我的任何判断不正确，每个数量代表什么？

Answer 1

p代表“产品”。如前所述，不变量是 p == i*j；算法会尝试 i 和 j 的不同组合，直到乘积 (p) 等于 n。如果它从不这样做（while 循环失败），您将得到 p != n，因此返回 n（n 是素数）。

在外部 while 循环体的末尾，j 是最大的整数，i 可以乘以得到 ≤ n 的值。

该算法避免显式除法，并尝试限制每个 i 检查的 j 个值的数量。在外层循环的开始，p==i*j 刚好小于 n。随着i逐渐增大，j需要逐渐缩小。在每个外部循环中，i 增加（并且 p 被更正以匹配不变量）。然后内循环减小 j（并更正 p）直到 p 再次 ≤ n。由于 i*j 在下一个外循环开始时仅小于 n，因此增加 i 会使乘积大于 n，然后重复该过程。

Answer 2

算法会尝试 1 和 n / i 之间的所有除数（继续过去 n / i 是没有用的，因为已经尝试过相应的商）。

所以外层循环实际执行

i= 1
while i * (n / i) != n && i < n / i)
{
  i++;
}

它通过避免分裂以一种聪明的方式做到了这一点。正如注释所说，保持不变 p = i * j ；更准确地说，p 是不超过 n 的 i 的最大倍数，这实际上建立了 j = n / i。 =27=]

当 i 递增时需要执行一些调整：i 变为 i + 1 使 p = i * j 变为 (i + 1) * j = p + j，并且 p 可能变得太大。这是通过根据需要 (j--, p-= i) 多次递减 j 来补偿来解决的。

这种找到给定数字的最小因子的方法如何工作？

How does this method, which finds the smallest factor of a given number, work?

language-agnostic

algorithm

factorization