找出差异最小的质数因子

Question

假设n，a，b是正整数，其中n不是素数，因此n=ab和a≥b和（a）−b） 越小越好。如果给定n，找到a和b值的最佳算法是什么？

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

Answer 1

一般的方法可以是：

>

回想一下，最简单的尝试除法，素数分解是通过反复尝试将奇数（或素数）增加到数的平方根以下来除数，然后将每个因子从数中除掉，从而按构造素数（n:=n/f）。

然后，懒洋洋地从n的素分解中依次枚举n的因子。生产一半后停止。找到了最接近平方根的n因子（不一定是素数），通过简单除法找到第二个因子。

如果这必须重复运行多次，那么预先计算n的平方根以下所需的素数将非常有用，以便在因式分解中使用。

Answer 2

首先......回答为什么你的方法

简单地求n的素因子并搜索其中a，b是n的因子且a-b最小化的组合

不是最优的：

假设你的号码是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。此外，这种方法的实施也很困难。

现在，为什么平方差的方法

表示S-n=Q，使得S和Q是完美的平方

这很好：

这是因为如果可以表示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））

另一种方法：

从楼层（sqrt（n））迭代到1。第一个数字（比如x），这样x |n将是所需对（a，b）中的一个数字。其他将是OBV，y=x/n。因此，您的答案将是y-x。

这是时间复杂算法。