寻找最接近某个值的公因数的有效算法？

我相信没有已知的有效（多项式时间）算法可以解决此问题，因为从整数分解到此问题的多项式时间都有所减少。由于没有已知的用于整数分解的多项式时间算法，因此也不可能存在针对您的问题的已知算法，因为否则我们确实会有用于整数分解的多项式时间算法。

要查看其工作原理，假设您有一个要分解的数字n。现在，使用您想要的任何算法，找到最接近√n的n和n的公因数。由于n的任何非平凡因数都不能大于√n，因此这将找到（1）除以n的最大整数，或者找到（2）如果n为质数的数字1。然后，您可以将n除以该数字并重复以产生n的所有因子。由于n最多具有O（log
n）个因数，因此对于您的问题，求解器最多需要多项式多次迭代，因此我们可以从整数分解到此问题的多项式时间减少。如上所述，这意味着，至少在公开文献中，没有解决该问题的已知有效经典算法。也许存在，但这将是非常重要的结果。

对不起，否定答案，希望对您有所帮助！