Как найти наименьшее общее кратное (LCM) для двух чисел

#java #c #math #lcm

#java #c #математика #lcm

Вопрос:

Я использовал метод Евклида, чтобы найти L.C.M для двух чисел.

 l.c.m=a*b/(gcd(a,b))

Как я могу это сделать, не используя этот алгоритм?
У меня есть идея сначала получить все множители этих двух чисел и сохранить их в массиве. Затем возьмите 1 элемент из массива 1 и найдите его в массиве 2, если он там присутствует, затем удалите его оттуда и сделайте результат умноженным на это число.

Это нормально?

1. Звучит как домашнее задание

2. Java или C ? Решения могут отличаться в зависимости от языка.

3. Лучше всего использовать (a / gcd(a,b)) * b , чтобы избежать переполнения целых чисел. Использование факторизации для вычисления lcm намного менее эффективно, чем использование gcd .

Ответ №1:

Почти. Что такое LCM 4 и 8? Очевидно, 8 (2 ³), но в вашем методе вы найдете 2. Вам нужно отслеживать не только все факторы, но и то, как часто они появляются.

1. Разве LCM из 4 и 8 на самом деле не 8, а не 4? И GCD (8,4) дает 4, поэтому (8*4)/4 = 8, значит, формула в вопросе порождает правильный ответ? LCM должен быть как минимум таким же большим, как большее из двух входных значений (при условии, что все положительные числа).

2. Да, исправлено. Методы GCD и LCM довольно тесно связаны. Если вы разложите оба члена на простые множители, возьмете соответствующие минимумы и умножите их, вы получите GCD (здесь: min (2,3) = 2, 2×2 = 4). Возьмите соответствующие максимумы (здесь: max (2,3) = 3, 2x2x2 = 8), и вы получите LCM.

Ответ №2:

Я считаю, что предлагаемый вами алгоритм представляет собой метод с использованием таблицы, проверьте, работает ли он для вас.

Ответ №3:

LCM (наименьшее общее кратное) всегда больше или равно большему из двух чисел. Итак, сначала мы проверим, что большее число само по себе является LCM из двух чисел, проверив, что большее число делится на меньшее, если да, мы нашли LCM, и если нет, то мы увеличим большее число на 1 и проверим снова.

 package com.company;
import java.util.Scanner;

public class Main {

public static void main(String args[]) {
    Scanner scan = new Scanner(System.in);
    System.out.print("Enter the first Number : ");
    int number1 = scan.nextInt();
    System.out.print("Enter the second number : ");
    int number2 =scan.nextInt();

    int multiple;

    if(number1 >= number2) {
        multiple = number1;
    } else {
        multiple = number2;
    }

    Boolean loopContinue = true;

    while(loopContinue) {
        if(multiple % number1 == 0 amp;amp; multiple % number2 == 0) {
            System.out.println("LCM of Two Numbers is "   multiple);
            loopContinue = false;
        }
        multiple  ;
    }
  }
}

Ответ №4:

Вы можете получить LCM из двух чисел, сначала получив GCD. Вот решение для вышеупомянутого.

 package com.practice.competitive.maths;

import java.util.Scanner;

public class LCMandGCD {

    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            int testCases = scanner.nextInt();
            while (testCases-- > 0) {
                long number1 = scanner.nextInt();
                long number2 = scanner.nextInt();
                long gcd = computeGCD(number1, number2);
                long lcm = computeLCM(number1, number2, gcd);
                System.out.println(lcm   " "   gcd);
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private static long computeGCD(long number1, long number2) {
        while (number1 != number2) {
            if (number1 > number2)
                number1 -= number2;
            else
                number2 -= number1;
        }   
        return number2;
    }

    private static long computeLCM(long number1, long number2, long gcd) {
        return (number1*number2)/gcd;
    }

}