找到最接近某个值的公约数的有效算法？
我有两个数字， x1和x2 。 对于数y ，我想计算x1和x2公约数尽可能接近y 。
有没有一个有效的算法呢？
我相信现在是时候改述我的问题，并且更加清楚。 这不是整数......所以说，我们有两个数字x1和x2 。 假设用户输入一个数字y 。 我想找到的数字y'接近于y因此x1 % y'和x2 % y'非常小（例如小于0.02 ，但让我们称这个数字为LIMIT ）。 换句话说，我不需要一个最佳算法，而是一个很好的近似值。
我感谢大家的时间和精力，这真的很友善！
我相信对这个问题没有已知的有效（多项式时间）算法，因为从整数分解到这个问题存在多项式时间减少。 由于没有已知的用于整数分解的多项式时间算法，因此您的问题不可能有已知的algortihm，否则我们确实会有整数因子分解的多项式时间算法。
要看看它是如何工作的，假设你有一个你想要考虑的数字n。 现在，使用任何你喜欢的算法，找出最接近√n的n和n的公因子。 由于n的平凡除数不能大于√n，因此它找到（1）除n的最大整数，或者（2）如果n是素数，则数字1。 然后你可以用n除以这个数字并重复产生n的所有因子。 由于n最多可以有O（log n）个因子，所以对于您的问题，这需要至多多项式求解器的多项式迭代，所以我们从整数因子分解到这个问题有一个多项式时间减少。 如上所述，这意味着，至少在公开文献中，没有已知的有效的经典算法来解决这个问题。 一个可能存在，但这将是一个非常重要的结果。
抱歉的否定答案，并希望这有助于！
这是有效的，因为我可以得到它：
from fractions import gcd
primes=[i for i in range(2,1000) if all(i%j!=0 for j in range(2,i))] #ensure you have enough primes.. (can improve efficency here)
def f(x1,x2,y):
_gcd=gcd(x1,x2)
if _gcd==1:
return 1
factors=(i for i in range(2,_gcd+1) if _gcd%i==0) #can improve efficiency here.. e.g. only go up to root(gcd)
r1=999999999
r2=999999999
for i in factors:
r1=min(r1,y%i)
r2=min(r2,i-y%i)
return y-r1 if r1<=r2 else y+r2
print f(8,4,3)
print f(16,12,5)
print f(997,53,44)
print f(2300*2,2300*3,57)
"""
2
4
1
56
"""
我想你可以通过贪心算法做，首先查找常用算法GCD命名d （这是在对数时间可计算的），然后找到的因素d ，每次分d到最小可用系数（创建d' ），并且比较|d'-y| with |dy| 如果是这样，小的继续（和替换d'与d ），否则，乘d'与最小消除的因素，再次它的距离比较为y。
上一篇: Efficient algorithm for finding a common divisor closest to some value?