寻找最接近某个值的公约数的高效算法？

Question

寻找最接近某个值的公约数的高效算法？

10

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

是否有高效的算法可以实现这一点？

我认为现在是重新表述我的问题并更加清晰的时候了。这不是关于整数的问题...... 所以，假设我们有两个数字x1和x2。假设用户输入一个数字y。我想要找到一个接近y的数字y'，使得x1％y'和x2％y'非常小(比如小于0.02，但是让我们称这个数字为LIMIT)。换句话说，我不需要最优算法，而是需要一个好的近似值。

感谢大家的时间和努力，你们真的很好！

- Fatso

我认为最好在新线程中询问它。 - Saeed Amiri

好的Saeed，我已经完成了：https://dev59.com/VGDVa4cB1Zd3GeqPbTxF - Fatso

4个回答

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

- Rusty Rob

2

我认为您可以使用贪心算法来解决此问题，首先使用常见的算法找到GCD并将其命名为d（可在对数时间内计算），然后找到d的因子，每次将d除以最小可用因子（创建d'），并将|d'-y|与|d-y|进行比较。如果更小，请继续这样做（并用d替换d'），否则，将d'乘以最小消除因子，再次将其距离与y进行比较。

- Saeed Amiri

2

那么你希望如何快速找到d的因数呢？只要我们在分解质因数时，应该先分解较小的数字（x1和x2），之后寻找最小公倍数就很容易了。 - BlueRaja - Danny Pflughoeft

4

@Saeed: 你怎么能假设d是一个小数？分解被认为是一个困难的问题——RSA公钥加密就依赖于这个事实！ - BlueRaja - Danny Pflughoeft

@BlueRaja-DannyPflughoeft，我希望你能提供比我更好的答案，然后告诉我我的答案很慢，那么我就可以理解你的投票反对了。目前你的投票反对真的很惊人！ - Saeed Amiri

@SaeedAmiri- 我很抱歉让你不高兴，但请不要朝我大喊大叫。我确实读了评论，我的评论是为了表明即使在你回复Blue Raja的帖子后，我仍然不同意你的推理。我对这个答案进行了反对投票，而不是其他答案，因为它仍然有非负分数，我想清楚地告诉社区我认为这个答案是错误的。 - templatetypedef

1

@SaeedAmiri 我点赞了你的回答，因为我认为人们在对这个问题进行负面评价。虽然没有完美的算法，但你的解决方案降低了简单暴力解决方案的复杂度。 - The Real Baumann

显示剩余11条评论

0

找到 x1 和 x2 的最大公约数。
如果 GCD <= Y，则返回 GCD。
当前最佳答案是 GCD，最佳距离为 GCD - y。
遍历所有数字 Y +/- [0 ... best distance]。
返回第一个既是 x1 的倍数又是 x2 的倍数的整数。

要找到最大公约数：

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;
}

我认为唯一的额外优化可能是将gcd因子分解（也许使用筛法？），正如@trinithis所建议的那样。

- The Real Baumann

1

-1 你的算法本质上是简单的暴力解决方案，但增加了额外的步骤。你只是在检查所有数字 Y +- n 直到找到一个。 - BlueRaja - Danny Pflughoeft

如果 Y 明显大于 GCD(x1, x2)，那么这是一个非常方便的优化。 - The Real Baumann

我很想知道为什么我的回答会被踩。这个解决方案是有效的，也没有更简单高效的解决方案了。期望一个不存在的万能方法似乎不足以拒绝我的答案。 - The Real Baumann

1

只是让你知道，我没有投反对票（实际上我投了赞成票）！这个网站总是有很多人投反对票。非常感谢你的努力。 - Fatso

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

我相信此问题没有已知的高效（多项式时间）算法，因为从整数分解到此问题存在多项式时间约简。由于整数分解没有已知的多项式时间算法，因此也没有已知的你的问题的算法，因为否则我们确实会有一个整数分解的多项式时间算法。

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

抱歉回答是否定的，希望这能有所帮助！