java - 2 つの数値の最小公倍数 (LCM) を見つける方法

Question

ユークリッドの方法を使用して、2 つの数値の最小公倍数を見つけました。

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

このアルゴリズムを使用せずにこれを行うにはどうすればよいですか? 最初にこれら 2 つの数値のすべての因数を取得し、それらを配列に格納するという考えがあります。次に、配列 1 から 1 つの要素を取得し、配列 2 でそれを検索します。そこに存在する場合は、そこから削除し、結果にその num を掛けます。

これでよろしいですか？

Answer 1

あなたが提案するアルゴリズムは、テーブルを使用する方法だと思います。それが機能するかどうかを確認してください。

Answer 2

ほとんど。4 と 8 の最小公倍数は? 明らかに 8 (2 ³ ) ですが、この方法では 2 が見つかります。すべての要因だけでなく、それらの出現頻度も追跡する必要があります。

Answer 3

最初に GCD を取得すると、2 つの数の 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;
    }

}