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

Question

У меня есть два номера, x1 и x2. Для номера y, я хочу рассчитать общий делитель x1 и x2 как можно ближе к y.

Есть ли эффективный алгоритм для этого?

---

Я считаю, что пришло время перефразировать мою проблему и быть более ясным. Это не о целых числах ... Итак, скажем, у нас есть два номера x1 и x2. Скажем, пользователь вводит номер y. Я хочу найти номер y', близкий к y, так что x1 % y' и x2 % y' очень маленькие (например, менее 0.02, но позвоните по этому номеру LIMIT). Другими словами, мне не нужен оптимальный алгоритм, но хорошее приближение.

Благодарю вас всех за ваше время и силы, это действительно любезно!

Answer 1

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

Чтобы увидеть, как это работает, предположим, что у вас есть число n, которое вы хотели бы учитывать.Теперь, используя любой алгоритм, который вам нужен, найдите общий коэффициент n и n, ближайший к √ n. Поскольку нетривиальный делитель n может быть больше √ n, это находит либо (1) наибольшее целое число, делящее n, либо (2) число 1, если n является простым. Затем вы можете разделить n на это число и повторить, чтобы получить все коэффициенты n. Поскольку n может иметь не более O (log n) факторов, для этого требуется не более полиномиально много итераций решателя для вашей задачи, поэтому мы имеем сокращение полиномиального времени от целочисленной факторизации к этой задаче. Как упоминалось выше, это означает, что, по крайней мере, в открытой литературе нет известного эффективного классического алгоритма для решения этой проблемы. Можно было бы существовать, но это был бы очень важный результат.

Извините за отрицательный ответ, и надеюсь, что это поможет!

Answer 2

1. Найти GCD 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); 
} 

Чтобы найти ближайший делитель к у ...

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.

Answer 3

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

Answer 4

Это эффективно, как я могу получить его:

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