Algoritmo eficiente para encontrar un divisor común más cercano a algún valor?

Question

Tengo dos números, x1 y x2. Para un número y, quiero calcular el divisor común de x1 y x2 lo más cerca posible de y.

¿Existe un algoritmo eficiente para esto?

---

creo que es hora de reformular mi problema y ser más clara. Esto no se trata de enteros ... Entonces, digamos que tenemos dos números x1 y x2. Digamos, el usuario ingresa un número y. Lo que quiero encontrar es un número y' cerca de y para que x1 % y' y x2 % y' sean muy pequeños (más pequeños que 0.02, por ejemplo, pero llamemos a este número LIMIT). En otras palabras, no necesito un algoritmo óptimo, sino una buena aproximación.

Gracias a todos por su tiempo y esfuerzo, ¡es realmente amable!

Answer 1

Creo que no se conoce ningún algoritmo eficiente (tiempo de polinomio) para este problema porque hay una reducción de tiempo polinomial desde integer factorization a este problema. Como no existe un algoritmo de tiempo polinomial conocido para la factorización de enteros, tampoco puede existir un algoritmo conocido para su problema, ya que de lo contrario tendríamos un algoritmo de tiempo polinomial para la factorización de enteros.

Para ver cómo funciona esto, supongamos que tiene un número n que le gustaría factorizar.Ahora, usando el algoritmo que desee, encuentre el factor común de n y n más cercano a √ n. Dado que ningún divisor no nivial de n puede ser mayor que √ n, esto encuentra (1) el entero más grande que divide n, o (2) el número 1 si n es primo. A continuación, puede dividir n por este número y repetir para producir todos los factores de n. Como n puede tener como máximo O (log n) factores, esto requiere como máximo polinomios muchas iteraciones del solucionador para su problema, por lo que tenemos una reducción del tiempo polinomial desde la factorización de enteros hasta este problema. Como se mencionó anteriormente, esto significa que, al menos en la literatura abierta, no se conoce un algoritmo clásico eficiente para resolver este problema. Uno podría existir, pero sería un resultado muy importante.

Disculpa la respuesta negativa, y espero que ayude!

Answer 2

1. Encuentra el GCD de x1 y x2.
2. Si GCD <= Y luego regresar GCD
3. actual mejor respuesta es GCD, con una mejor distancia de GCD - y.
4. iterar a través de todos los números Y +/- [0 ... mejor distancia]
5. devolver el primer número entero que es un múltiplo de ambos x1 y x2

Para encontrar el MCD

public int getGCD(int a, int b) 
{ 
    return (b==0) ? a : gcd(b, a%b); 
} 

para encontrar el divisor más cercano a 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; 
} 

creo que la junta Una optimización adicional disponible sería factorizar el gcd (¿quizás usando un tamiz?) como lo sugirió @trinithis.

Answer 3

creo que puede hacerlo por el algoritmo codicioso, en primer lugar encontrar GCD por algoritmos comunes nombrarlo d (que es computable en el tiempo logarítmica) y luego encontrar factores de d cada vez se dividen d al factor más pequeño disponible (Crear d'), y compare |d'-y| con |d-y| si es más pequeño continúe de esta manera (y reemplace d' con d), sino, multiplique d' con el factor eliminado más pequeño, y nuevamente compare su distancia a y.

Answer 4

Esta es eficiente como puedo conseguirlo:

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