Каков наиболее эффективный способ вычисления наименьшего общего кратного из двух целых чисел?

Question

Каков наиболее эффективный способ вычисления наименьшего общего кратного из двух целых чисел?

Я только что придумал это, но это определенно оставляет желать лучшего.

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

Наименьшее общее кратное (lcm) a и b - это их произведение, деленное на их наибольший общий делитель (gcd) (т.е. lcm(a, b) = ab/gcd(a,b))

Итак, возникает вопрос, как найти gcd? Евклидов алгоритм - это, как правило, способ вычисления gcd.Прямая реализация классического алгоритма эффективна, но есть вариации, которые используют преимущества двоичной арифметики, чтобы сделать ее немного лучше.См. Кнут" Искусство компьютерного программирования " Том 2, "Полу численные алгоритмы" § 4.5.2 .

Answer 2

Помните, что наименьшее общее кратное - это наименьшее целое число, кратное каждому из двух или более чисел.

Если вы пытаетесь вычислить LCM из трех целыхвыполните следующие действия:

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

Запишите простую факторизацию для каждого числа.19 - простое число.Вам не нужно множить 19.

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

Повторите каждый простой множитель наибольшее количество раз, которое он встречает в любой из простых простых факторизаций выше.798

Наименьшее общее кратное 21, 42 и 19 равно 798.

Answer 3

Я думаю, что подход "сокращения на самый большой общий делитель " должен быть быстрее. Начните с вычисления GCD (например, используя алгоритм Евклида ), затем разделите произведение двух чисел на GCD.

Answer 4

Лучшее решение на C ++ ниже без переполнения

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

Я не знаю, оптимизирован он или нет, но, вероятно, самый простой:

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 6

Прежде всего, вы должны найти самый большой общий делитель

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

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

}

После этого, используя GCD, вы можете легко найти наименьшее общее кратное, как это

lcm = a / gcd * b;

Answer 7

Фрагмент кода евклидова GCD

int findGCD(int a, int b) {
        if(a < 0 || b < 0)
            return -1;

        if (a == 0)
            return b;
        else if (b == 0)
            return a;
        else 
            return findGCD(b, a % b);
    }

Answer 8

Произведение из 2 чисел равно LCM * GCD или HCF.Поэтому лучший способ найти LCM - найти GCD и разделить продукт с GCD.То есть LCM (a, b) = (a * b) / GCD (a, b).

Answer 9

C ++ шаблон. Время компиляции

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

Возьмите последовательные числа, кратные большему из двух чисел, пока результат не станет кратным меньшему.

это может сработать ..

   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;
   }