algorithm - 找到使差异尽可能最小的质因数

Question

假设n、a、b是正整数，其中n不是素数，使得n=ab且a≥b且(a−b)尽可能小。如果给定 n，找到 a 和 b 值的最佳算法是什么？

我读到了一个解决方案，他们试图通过搜索大于 n 的平方 S 来将 n 表示为两个平方之间的差，使得 S - n =(另一个平方)。为什么这比简单地找到 n 的质因数并搜索 a,b 是 n 的因数且 a - b 最小化的组合更好？

Answer 1

首先......回答你的方法的原因

simply finding the prime factors of n and searching for the combination where a,b are factors of n and a - b is minimized

不是最佳的:

假设您的号码是 n = 2^7 * 3^4 * 5^2 * 7 * 11 * 13 (=259459200)，完全在 int 范围内。从组合理论来看，这个数字正好有 (8 * 5 * 3 * 2 * 2 * 2 = 960) 因子。因此，首先找到所有这 960 个因子，然后找到所有满足 a * b = n 的对 (a,b)，在本例中为 (6C1 + 9C2 + 11C3 + 13C4 + 14C5 + 15C6 + 16C7 + 16C8) 方式。 (如果我没记错的话，我的组合学有点弱)。如果实现最佳的话，其数量级为1e5。而且，这种方法的实现很困难。

现在，为什么要采用平方差法

represent S - n = Q, such that S and Q are perfect squares

很好:

这是因为如果您可以表示 S - n = Q，则意味着 n = S - Q

=> n = s^2 - q^2
=> n = (s+q)(s-q)
=> Your reqd ans = 2 * q

现在，即使您迭代所有方格，当两个连续方格的差值大于 n 时，您要么找到答案，要么终止

但我不认为这对所有 n 都是可行的(例如，如果 n=6，则没有 (S,Q )。)

Another approach:

从 floor(sqrt(n)) 迭代到 1。第一个数字(例如 x)，这样 x|n 将是以下数字之一所需的对(a,b)。其他将为 obvs，y = x/n。所以，你的答案将是y - x。

这是O(sqrt(n))时间复杂度算法。