Что самый эффективный путь состоит в том, чтобы вычислить наименьшее общее кратное двух целых чисел?
Что самый эффективный путь состоит в том, чтобы вычислить наименьшее общее кратное двух целых чисел?
Я просто придумал это, но это определенно оставляет желать лучшего.
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 );
3 ответа
Наименьшее общее кратное (lcm) a и b - это их произведение, деленное на их наибольший общий делитель (gcd) (т.е. lcm (a, b) = ab / gcd (a, b) ).
Итак, возникает вопрос, как найти gcd? Евклидов алгоритм обычно используется для вычисления gcd. Прямая реализация классического алгоритма эффективна, но есть варианты, которые используют двоичную арифметику, чтобы добиться большего. См. Кнута « Искусство компьютерного программирования » Том 2, «Полуучисленные алгоритмы» § 4.5.2 .
Я думаю, что подход « редукции с помощью наибольшего общего делителя » должен быть быстрее. Начните с вычисления НОД (например, используя алгоритм Евклида ), затем разделите произведение двух чисел на НОД.
Последовательно умножайте большее из двух чисел, пока результат не станет кратным меньшему.
это может сработать ..
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;
}