我有两个号码，x1 and x2。对于一个号码y，我想计算的公约数x1 and x2尽可能接近y.
有一个有效的算法吗？
我相信是时候重新表述我的问题并且更加清楚了。这与整数无关......
所以，假设我们有两个数字x1 and x2。比如说，用户输入一个数字y。我想要找到的是一个数字y'相近y以便x1 % y' and x2 % y'非常小（小于0.02，例如，但让我们拨打这个号码LIMIT）。换句话说，我不需要最优算法，而是一个好的近似值。
我感谢大家付出的时间和精力，真是太好了！
我相信对于这个问题没有已知的有效（多项式时间）算法，因为存在多项式时间减少整数分解对于这个问题。由于没有已知的用于整数分解的多项式时间算法，因此也不存在用于您的问题的已知算法，因为否则我们确实会有一个用于整数分解的多项式时间算法。
要了解其工作原理，假设您有一个要分解的数字 n。现在，使用您想要的任何算法，找到 n 和最接近 √n 的 n 的公因数。由于 n 的非平凡除数不能大于 √n，因此可以找到 (1) 可整除 n 的最大整数，或 (2) 如果 n 是素数，则找到数字 1。然后，您可以将 n 除以该数字并重复以产生 n 的所有因数。由于 n 最多可以有 O(log n) 个因子，因此这最多需要对问题的求解器进行多项式多次迭代，因此我们从整数因式分解到此问题进行了多项式时间缩减。如上所述，这意味着，至少在公开文献中，还没有已知的有效经典算法来解决这个问题。一个可能存在，但这将是一个非常重要的结果。
很抱歉给出否定的答案，希望这对您有所帮助！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
