Эффективный алгоритм поиска общего делителя, ближайшего к некоторому значению?

Я считаю, что для этой задачи не существует известного эффективного (полиномиального времени) алгоритма, потому что существует полиномиальное сокращение от целочисленная факторизация к этой проблеме. Поскольку не существует известного алгоритма с полиномиальным временем для целочисленной факторизации, не может быть известного алгоритма и для вашей задачи, поскольку в противном случае у нас действительно был бы алгоритм с полиномиальным временем для целочисленной факторизации.

Чтобы увидеть, как это работает, предположим, что у вас есть число n, которое вы хотите разложить на множители. Теперь, используя любой алгоритм, найдите общий делитель n и n, ближайший к n. Поскольку ни один нетривиальный делитель n не может быть больше n, это находит либо (1) наибольшее целое число, которое делит n, либо (2) число 1, если n простое. Затем вы можете разделить 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
"""

Я думаю, вы можете сделать это с помощью жадного алгоритма, сначала найдите НОД с помощью обычных алгоритмов, назовите его d (который вычисляется в логарифмическом времени), затем найдите множители d каждый раз, разделите d на наименьший доступный множитель (создайте d') и сравните |d'-y| с |d-y| если меньше, продолжайте в том же духе (и замените d' на d), в противном случае умножьте d' на наименьший исключенный множитель и снова сравните его расстояние с y.

1. Найдите НОД x1 и x2.
2. Если GCD <= Y, то вернуть GCD
3. Текущий лучший ответ – GCD, с лучшим расстоянием – GCD - y.
4. Перебрать все числа Y +/- [0 ... лучшее расстояние]
5. Возвращает первое целое число, кратное как 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.