找到使差异尽可能小的主要因素
Find prime factors such that difference is smallest as possible
假设n,a,b是正整数，n不是素数，使得n=ab且a≥b且(a−b)越小越好。如果给定 n，求 a 和 b 值的最佳算法是什么？
我读了一个解决方案，他们试图通过搜索大于 n 的正方形 S 将 n 表示为两个正方形之间的差值，使得 S - n =（另一个正方形）。为什么这会比简单地找到 n 的质因数并搜索其中 a、b 是 n 的因数并且 a - b 最小化的组合更好？
首先....回答为什么你的方法
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) 使得 a * b = n，在这种情况下将是 (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
现在，即使您对所有方块进行迭代，您也会找到答案或在 2 个连续方块的差异大于 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))时间复杂度算法。
一个通用的方法可能是这样的：
求出你的数的质因数分解：n = Π piai。除了 n 是素数或半素数的最坏情况外，这将比 O(n1/2) 快得多迭代的时间从平方根开始向下，这不会将找到的因子从数字中除掉。
Recall 最简单的试验除法素数分解是通过重复尝试通过增加奇数（或质数）来除以数字的平方根以下的数字，除以每个因数-- 因此通过构造素数 -- 发现 (n := n/f).
然后，惰性地从它的质因数分解。生产一半后停止。找到最接近其平方根的 n 的（不一定是质数）因子后，通过简单除法找到第二个因子。
万一这必须重复运行很多次，预先计算出n的平方根以下所需的素数，将大有裨益，用于分解。
假设n,a,b是正整数，n不是素数，使得n=ab且a≥b且(a−b)越小越好。如果给定 n，求 a 和 b 值的最佳算法是什么？
我读了一个解决方案，他们试图通过搜索大于 n 的正方形 S 将 n 表示为两个正方形之间的差值，使得 S - n =（另一个正方形）。为什么这会比简单地找到 n 的质因数并搜索其中 a、b 是 n 的因数并且 a - b 最小化的组合更好？
首先....回答为什么你的方法
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) 使得 a * b = n，在这种情况下将是 (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
现在，即使您对所有方块进行迭代，您也会找到答案或在 2 个连续方块的差异大于 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))时间复杂度算法。
一个通用的方法可能是这样的：
求出你的数的质因数分解：n = Π piai。除了 n 是素数或半素数的最坏情况外，这将比 O(n1/2) 快得多迭代的时间从平方根开始向下，这不会将找到的因子从数字中除掉。
Recall 最简单的试验除法素数分解是通过重复尝试通过增加奇数（或质数）来除以数字的平方根以下的数字，除以每个因数-- 因此通过构造素数 -- 发现 (
n := n/f).然后，惰性地
万一这必须重复运行很多次，预先计算出n的平方根以下所需的素数，将大有裨益，用于分解。