找到最接近某个值的公约数的有效算法？

Question

我有两个数字，x1 和 x2。对于数字y，我想计算尽可能接近y的x1和x2的公约数。

有一个有效的算法吗？

---

我认为是时候重新表述我的问题并使其更加清晰。这与整数无关...... 因此，假设我们有两个数字 x1 和 x2。比如说，用户输入一个数字y。我想找到的是一个接近于 y 的数字 y'，这样 x1 % y' 和 x2 % y'< /code> 非常小（例如小于 0.02，但我们称这个数字为 LIMIT）。换句话说，我不需要最优算法，而是一个好的近似值。

我感谢大家付出的时间和精力，真是太好了！

Answer 1

我相信这个问题没有已知的有效（多项式时间）算法，因为从 整数分解来解决这个问题。由于没有已知的用于整数分解的多项式时间算法，因此也不存在用于您的问题的已知算法，因为否则我们确实会有一个用于整数分解的多项式时间算法。

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

很抱歉给出否定的答案，希望这对您有所帮助！

Answer 2

这是有效的，因为我可以得到它：

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
"""

Answer 3

我认为你可以通过贪心算法来做到这一点，首先通过常见算法找到GCD，将其命名为d（可以用对数时间计算），然后每次除<时找到d的因子< code>d 为最小可用因子（创建 d'），并将 |d'-y| 与 |dy| 进行比较如果更小，继续以这种方式（并替换d' 与 d），否则，将 d' 与最小消除因子相乘，并再次将其距离与 y 进行比较。

Answer 4

1. 求 x1 和 x2 的 GCD。
2. 如果 GCD <= Y 则返回 GCD
3. 当前最佳答案是 GCD，最佳距离为 GCD - y >。
4. 迭代所有数字 Y +/- [0 ... 最佳距离]
5. 返回同时为 x1 和 x2 倍数的第一个整数

查找 GCD

public int getGCD( int a, int b )
{
   return (b==0) ? a : gcd(b, a%b);
}

查找最接近的除数到 y...

public int closestDivisor( int a, int b, int y ){
    int gcd = getGCD( a, b );
    if( gcd <= y ) return gcd;
    int best = gcd - y;
    for( int i = 0; i < best; i++ )
    {
        if( gcd % (i-y) == 0 ) return i - y;
        if( gcd % (i+y) == 0 ) return i + y;
    }
    return gcd;
}

我相信唯一可用的额外优化是按照 @trinithis 的建议分解 gcd（也许使用筛子？）。