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

Question

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

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

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

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

Answer 1

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 && multiple % number2 == 0) {
            System.out.println("LCM of Two Numbers is " + multiple);
            loopContinue = false;
        }
        multiple++;
    }
  }
}

Answer 2

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

Answer 3

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

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

}