How to find the highest GCD of 2 numbers such that the 2 numbers are from a given range of numbers?

A number X is a possible gcd of two numbers in the range if there's two multiples of X in the range.

So we need to find the largest X such that there's m such that mX >= lower_bound and (m+1)X <= upper_bound.

For a given m, the largest X that satisfies this (if any) is X = floor(upper_bound / (m+1)), if floor(upper_bound/(m+1)) * m >= lower_bound. Note that a larger m will give a smaller X, so we need to find the smallest possible m to find the largest X.

Now we can just try m=1, m=2, and so on until we find an X (which will be largest possible X).

Note that we've sneakily avoided anything to do with gcd: if we find the largest X such that there's two multiples of X in the range, then necessarily those two multiples of X must have gcd X. And we can find the largest such X by finding the smallest m such that mX and (m+1)X are both in the range (and picking the largest such X for that m).

For example:

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

Output:

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

(note: an earlier edit of this answer used binary search to find m and x. That was wrong because the existence of x for a particular m is not monotonic).

Going to use lower and upper (dropping _bound) and gcd for GCD(X, Y).
For lower below floor(upper/2), gcd is close to the latter.
For lower close to upper, upper - lower is an upper bound.

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

(Using v - v%c is just alternative to the f = v // c, f*c Paul Hankin has used.
I don't prefer one over the other. (Or introduce a floor_multiple(n, factor) for a single occurrence.))
(This was in a company's coding round  A real PITA! Or just checking if you bite the bullet and code a quality solution "fast enough until experience suggest otherwise" you fully well know to be dissatisfying in performance.)