如何找到2个数字的最高GCD，使得2个数字来自给定的数字范围？-编程知识-白鹭情

问题：

给定一个输入(lower_bound, upper_bound)，计算：

max{ GCD(X,Y), (X,Y) satisfying lower_bound <= X < Y <= upper_bound }

例子：

INPUT: lower_bound = 1, upper_bound = 100000
OUTPUT: 50000, obtained with X=50000, Y=100000

INPUT: lower_bound = 3, upper_bound = 4
OUTPUT: 1, obtained with X=3, Y=4

这是在一家公司的编码回合中，基本上找到所有可能对的 GCD 的蛮力方法不起作用。

它在示例测验用例上作业，但在提交期间对隐藏的测验用例超时。

众所周知，输入的 lower_bound 和 upper_bound 将始终介于 1 和 1000000 之间。

uj5u.com热心网友回复：

如果范围内有两个 X 的倍数，则数字 X 可能是范围内两个数字的 gcd。

所以我们需要找到最大的 X 使得有 m 使得 mX >= lower_bound 并且 (m 1)X <= upper_bound。

对于给定的 m，如果 floor(upper_bound/(m 1)) * m >= lower_bound，则满足此条件的最大 X（如果有）是 X = floor(upper_bound / (m 1))。请注意，较大的 m 将给出较小的 X，因此我们需要找到可能的最小 m 来找到最大的 X。

现在我们可以尝试 m=1、m=2 等等，直到我们找到一个 X（这将是最大可能的 X）。

请注意，我们偷偷地避免与 gcd 有任何关系：如果我们找到最大的 X 使得范围内有两个 X 的倍数，那么这两个 X 的倍数必然有 gcd X。我们可以找到最大的 X通过找到最小的 m 使得 mX 和 (m 1)X 都在范围内（并为那个 m 选择最大的 X）。

例如：

def findX(lower, upper):
    for m in range(1, lower 1):
        x = upper // (m   1)
        if x * m >= lower:
            return 'input:%d,%d => %d, obtained with X=%d, Y=%d' % (lower, upper, x, x * m, x * (m 1))

print(findX(3, 4))
print(findX(10000, 10010))
print(findX(50000, 99999))
print(findX(50000, 100000))

输出：

input:3,4 => 1, obtained with X=3, Y=4
input:10000,10010 => 10, obtained with X=10000, Y=10010
input:50000,99999 => 33333, obtained with X=66666, Y=99999
input:50000,100000 => 50000, obtained with X=50000, Y=100000

（注意：此答案的早期编辑使用二进制搜索来查找 m 和 x。这是错误的，因为特定 m 的 x 的存在不是单调的）。

uj5u.com热心网友回复：

将使用lower和upper（洗掉_bound）和gcd作为 GCD(X, Y)。
对于较低的楼层（upper/2），gcd 接近后者。
对于接近上限的下限，上限 - 下限是上限。

from math import sqrt, ceil

def highest_GCD(lower, upper, mess=(__name__ == '__main__')):
    """ Return max{ GCD(X, Y) such that lower <= X < Y <= upper }. """
    # ToDo: useful test cases
    if not 0 < lower < upper:
        return None if not mess else None, 'No GCD for lack of numbers'
    limit = ceil(sqrt(upper))  # one factor got to be smaller
    gap = upper - lower
    candidates = (upper // factor for factor in range(upper // gap, limit)
        ) if limit < gap else range(gap, 0, -1)
    for candidate in candidates:
        higher = upper - upper % candidate
        if lower <= higher - candidate:
            return candidate if not mess else (
                candidate, 'highest GCD in [%d, %d] is %d, dividing X=%d, Y=%d' % (
                       lower, upper, candidate, higher - candidate, higher))

（使用v - v%c仅仅是替代f = v // c，f*c 保罗·汉金已经习惯了。
我不喜欢一个比其他（或引进一个floor_multiple(n, factor)单个发生。））
（This was in a company's coding round ?一个真正的PITA！或者只是如果你硬着头皮代码检查质量解决方案“足够快，直到经验表明并非如此”您完全知道性能不满意。）