math - para - mcm y mcd explicacion

¿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

Creo que el enfoque de " reducción por el mayor divisor común " debería ser más rápido. Comience por calcular el GCD (por ejemplo, usando el algoritmo de Euclides ), luego divida el producto de los dos números por el GCD.

Answer 2

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

Entonces, la pregunta es, ¿cómo encontrar el gcd? El algoritmo euclidiano generalmente es 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. Ver el " Volumen 2" de Knuth " El arte de la programación de computadoras " , "Algoritmos de Seminumerical" § 4.5.2 .

Answer 3

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

Answer 4

En primer lugar, debes encontrar el mayor divisor común

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

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

}

Después de eso, usando el GCD puedes encontrar fácilmente el mínimo común múltiplo como este

lcm = a / gcd * b;

Answer 5

La mejor solución en C ++ a continuación sin desbordamiento

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

Plantilla C ++. 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 8

Tome múltiplos sucesivos 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 9

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

Si está tratando de descubrir el LCM de tres enteros, siga estos pasos:

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

Escribe la factorización prima para cada número. 19 es un número primo. No necesita factorizar 19.

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

Repita cada factor primo la mayor cantidad de veces que aparece en cualquiera de las factorizaciones primarias anteriores.

2 × 3 × 7 × 19 = 798

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