如何求两个数的最小公倍数 (LCM)

Question

我已经使用欧几里得的方法来找到两个数字的最小公倍数。

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

如果不使用这个算法我该如何做到这一点？ 我的想法是首先获取这两个数字的所有因数并将它们存储在数组中。然后从数组 1 中取出 1 个元素并在数组 2 中搜索它，如果它存在，则从那里删除它并使结果乘以该数字。

这样可以吗？

Answer 1

几乎。 4 和 8 的 LCM 是多少？显然是 8 (2³)，但在您的方法中您会发现 2。您不仅需要跟踪所有因素，还需要跟踪它们出现的频率。

Answer 2

我相信您建议的算法是使用表格的方法，请检查看看它是否适合你。

Answer 3

LCM（最小公倍数）始终大于或等于两个数字中的较大者。因此，我们首先检查较大的数字本身是否是两个数字的 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 4

**使用 while 循环的两个数字的 LCM**

package whileloop1;

import java.util.Scanner;

public class Lcm {

public static void main(String[] args) {
    Lcm obj = new Lcm();
    obj.twoNumberLcm();
}
void twoNumberLcm       
{
    Scanner Sobj = new Scanner(System.in);
    System.out.println("Enter your First Number ");
    int num1 = Sobj.nextInt();
    System.out.println("Enter your Second Number ");
    int num2 = Sobj.nextInt();
    int big,small;
    if(num1>num2)
    {
        big = num1;
        small = num2;
    }
    else
    {
        big = num2;
        small = num1;
    }
    System.out.println(" Bigger number is " + big);
    System.out.println(" Smaller number is " + small);
    int smallcopy = small;
    int bigcopy = big;
    int count =1;
    while(count>0)
    {
        while(big>=small)
        {
            if(big == small)
            {
                System.out.println("Least common mutiples of given two numbers" + small);
                count--;
                break;
            }
            small=small+smallcopy;
        }
        big = big+bigcopy;
    }
}

Answer 5

首先得到GCD就可以得到两个数的最小公倍数（LCM）。
这是上述问题的解决方案。

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

}