¿Cuál es la forma más eficiente de calcular el mínimo común múltiplo de dos enteros?

Question

¿Cuál es la forma más eficiente de calcular el mínimo común múltiplo de dos enteros?

Me acabo de ocurrir esto, pero definitivamente deja algo que desear.

int n=7, m=4, n1=n, m1=m; 

while(m1 != n1){ 
    if(m1 > n1) 
     n1 += n; 
    else 
     m1 += m; 
} 

System.out.println("lcm is " + m1); 

Answer 1

El menos común múltiplo (lcm) de a y b es su producto dividido por su máximo común divisor (mcd) (es decir lcm(a, b) = ab/gcd(a,b)).

Entonces, la pregunta es ¿cómo encontrar el gcd? El Euclidean algorithm es generalmente cómo se calcula el gcd. La implementación directa del algoritmo clásico es eficiente, pero hay variaciones que aprovechan la aritmética binaria para mejorar un poco. Consulte Knuth en "The Art of Computer Programming" Volume 2, "Seminumerical Algorithms" § 4.5.2.

Answer 2

Tome sucesivos múltiplos del mayor de los dos números hasta que el resultado sea un múltiplo de los más pequeños.

esto podría funcionar ..

public int LCM(int x, int y) 
    { 
     int larger = x>y? x: y, 
      smaller = x>y? y: x, 
      candidate = larger ; 
     while (candidate % smaller != 0) candidate += larger ; 
     return candidate; 
    } 

Answer 3

Creo que el enfoque de "reduction by the greatest common divider" debería ser más rápido. Comience por calcular el GCD (por ejemplo, usando Euclid's algorithm), luego divida el producto de los dos números por el GCD.

Answer 4

Recuerde El mínimo común múltiplo es el menor número entero que es un múltiplo de cada uno de dos o más números.

Si usted está tratando de averiguar el mcm de tres enteros, siga estos pasos:

**Find the LCM of 19, 21, and 42.** 

Escribir la descomposición en factores primos de cada número. 19 es un número primo. Usted no necesita un factor 19.

21 = 3 × 7 
42 = 2 × 3 × 7 
19 

Repetir cada factor primordial el mayor número de veces que aparece en cualquiera de los anteriores factores primos.

2 x 3 x 7 x 19 = 798

El mínimo común múltiplo de 21, 42, y 19 es 798.

Answer 5

En primer lugar, usted tiene que encontrar el máximo común divisor

for(int = 1; i <= a && i <= b; i++) { 

    if (i % a == 0 && i % b == 0) 
    { 
     gcd = i; 
    } 

} 

Después de eso, el uso de la GCD podrá encontrar fácilmente el mínimo común múltiplo como esto

lcm = a/gcd * b; 

Answer 6

No sé si está optimizado o no, pero probablemente el más fácil:

public void lcm(int a, int b) 
{ 
    if (a > b) 
    { 
     min = b; 
     max = a; 
    } 
    else 
    { 
     min = a; 
     max = b; 
    } 
    for (i = 1; i < max; i++) 
    { 
     if ((min*i)%max == 0) 
     { 
      res = min*i; 
      break; 
     } 
    } 
    Console.Write("{0}", res); 
} 

Answer 7

La mejor solución en C++ a continuación, sin desbordar

#include <iostream> 
using namespace std; 
long long gcd(long long int a, long long int b){   
    if(b==0) 
     return a; 
    return gcd(b,a%b); 
} 

long long lcm(long long a,long long b){  
    if(a>b) 
     return (a/gcd(a,b))*b; 
    else 
     return (b/gcd(a,b))*a;  
} 

int main() 
{ 
    long long int a ,b ; 
    cin>>a>>b; 
    cout<<lcm(a,b)<<endl;   
    return 0; 
} 

Answer 8

C++ plantilla.Tiempo de compilación

#include <iostream> 

const int lhs = 8, rhs = 12; 

template<int n, int mod_lhs=n % lhs, int mod_rhs=n % rhs> struct calc { 
    calc() { } 
}; 

template<int n> struct calc<n, 0, 0> { 
    calc() { std::cout << n << std::endl; } 
}; 

template<int n, int mod_rhs> struct calc<n, 0, mod_rhs> { 
    calc() { } 
}; 

template<int n, int mod_lhs> struct calc <n, mod_lhs, 0> { 
    calc() { } 
}; 

template<int n> struct lcm { 
    lcm() { 
    lcm<n-1>(); 
    calc<n>(); 
    } 
}; 

template<> struct lcm<0> { 
    lcm() {} 
}; 

int main() { 
    lcm<lhs * rhs>(); 
} 

Answer 9

El producto de 2 números es igual a LCM * GCD o HCF. Entonces la mejor manera de encontrar el LCM es encontrar GCD y dividir el producto con GDC