1. 概要

2つの非ゼロ整数(a、b)最小公倍数(LCM)は、aとの両方で完全に割り切れる最小の正の整数です。 X166X]b。

このチュートリアルでは、2つ以上の数値のLCMを見つけるためのさまざまなアプローチについて学習します。 負の整数とゼロはLCMの候補ではないことに注意する必要があります。

2. 単純なアルゴリズムを使用して2つの数値のLCMを計算する

乗算が加算を繰り返すという単純な事実を使用して、2つの数値のLCMを見つけることができます。

2.1. アルゴリズム

LCMを見つけるための単純なアルゴリズムは、2つの数値のLCMのいくつかの基本的なプロパティを利用する反復アプローチです。

まず、ゼロのある任意の数のLCMはゼロ自体であることがわかります。 したがって、指定された整数のいずれかが0の場合はいつでも、プロシージャを早期に終了できます。

次に、2つの非ゼロ整数のLCMの下限が、2つの数値の絶対値の大きい方であるという事実を利用することもできます。

さらに、前に説明したように、LCMが負の整数になることはありません。 したがって、整数の絶対値のみを使用して、最小公倍数が見つかるまで可能な倍数を見つけます。

lcm(a、b)を決定するために従う必要のある正確な手順を見てみましょう。

  1. a=0またはb=0の場合は、lcm(a、b)= 0で戻ります。それ以外の場合は、手順2に進みます。
  2. 2つの数値の絶対値を計算します。
  3. 手順2で計算された2つの値の高い方としてlcmを初期化します。
  4. lcmが低い絶対値で割り切れる場合は、を返します。
  5. 2つの中でより高い絶対値でlcmをインクリメントし、ステップ4に進みます。

この単純なアプローチの実装を開始する前に、ドライランを実行してlcm(12、18)を見つけましょう。

12と18の両方が正なので、ステップ3にジャンプして、lcm = max(12、18)= 18を初期化し、さらに進みます。

最初の反復では、lcm = 18であり、これは12で完全に割り切れません。 したがって、18ずつインクリメントして続行します。

2番目の反復では、lcm = 36であり、12で完全に割り切れることがわかります。 したがって、アルゴリズムから戻って、lcm(12、18)は36であると結論付けることができます。

2.2. 実装 

Javaでアルゴリズムを実装しましょう。 lcm()メソッドは、2つの整数引数を受け入れ、それらのLCMを戻り値として指定する必要があります。

上記のアルゴリズムには、絶対値、最小値、最大値の検索など、数値に対していくつかの数学演算を実行することが含まれていることがわかります。 この目的のために、 abs() min()、 max()などのMathクラスの対応する静的メソッドを使用できます。それぞれ

lcm()メソッドを実装しましょう。

public static int lcm(int number1, int number2) {
    if (number1 == 0 || number2 == 0) {
        return 0;
    }
    int absNumber1 = Math.abs(number1);
    int absNumber2 = Math.abs(number2);
    int absHigherNumber = Math.max(absNumber1, absNumber2);
    int absLowerNumber = Math.min(absNumber1, absNumber2);
    int lcm = absHigherNumber;
    while (lcm % absLowerNumber != 0) {
        lcm += absHigherNumber;
    }
    return lcm;
}

次に、このメソッドも検証しましょう。

@Test
public void testLCM() {
    Assert.assertEquals(36, lcm(12, 18));
}

上記のテストケースは、lcm(12、18)が36であると主張することにより、 lcm()メソッドの正しさを検証します。

3. 素因数分解アプローチの使用

算術の基本定理は、1より大きいすべての整数を素数の累乗の積として一意に表現できると述べています。

したがって、任意の整数N> 1の場合、N =(2 k1 )*(3 k2 )*(5 k3 )*…

この定理の結果を使用して、2つの数値のLCMを見つけるための素因数分解アプローチを理解します。

3.1. アルゴリズム

素因数分解アプローチは、2つの数の素数分解からLCMを計算します。 素因数分解の素因数と指数を使用して、2つの数値のLCMを計算できます。

いつ、| a | =(2 p1 )*(3 p2 )*(5 p3 )*…および| b | =(2 q1 )*(3 q2 )*(5 q3 )*…次に、 lcm(a、b)=(2max( p1、q1))*(3max(p2、q2))*(5max(p3、q3))…

このアプローチを使用して12と18のLCMを計算する方法を見てみましょう。

まず、2つの数値の絶対値を素数の積として表す必要があります。12= 2 * 2 *3=2²*3¹18=2* 3 *3=2¹*3²

ここで、上記の表現の主な要因は2と3であることがわかります。

次に、LCMの各素因数の指数を決定しましょう。 これを行うには、2つの表現からより高いパワーを取得します。

この戦略を使用すると、LCMの2の累乗はmax(2、1)= 2になり、LCMの3の累乗はmax(1、2)=2になります。

最後に、前のステップで得られた対応するパワーで素数を乗算することにより、LCMを計算できます。 したがって、lcm(12、18)=2²*3²=36になります。

3.2. 実装

私たちのJava実装は、LCMを見つけるために2つの数値の素因数分解表現を使用します。

この目的のために、 getPrimeFactors()メソッドは整数引数を受け入れ、その素因数分解表現を提供する必要があります。 Javaでは、 HashMap を使用して数値の素因数分解を表すことができます。ここで、各キーは素因数を示し、キーに関連付けられた値は対応する素因数の指数を示します。

getPrimeFactors()メソッドの反復実装を見てみましょう。

public static Map<Integer, Integer> getPrimeFactors(int number) {
    int absNumber = Math.abs(number);

    Map<Integer, Integer> primeFactorsMap = new HashMap<Integer, Integer>();

    for (int factor = 2; factor <= absNumber; factor++) {
        while (absNumber % factor == 0) {
            Integer power = primeFactorsMap.get(factor);
            if (power == null) {
                power = 0;
            }
            primeFactorsMap.put(factor, power + 1);
            absNumber /= factor;
        }
    }

    return primeFactorsMap;
}

12と18の素因数分解マップはそれぞれ{2→2、3→1}と{2→1、3→2}であることがわかっています。 これを使用して、上記の方法をテストしてみましょう。

@Test
public void testGetPrimeFactors() {
    Map<Integer, Integer> expectedPrimeFactorsMapForTwelve = new HashMap<>();
    expectedPrimeFactorsMapForTwelve.put(2, 2);
    expectedPrimeFactorsMapForTwelve.put(3, 1);

    Assert.assertEquals(expectedPrimeFactorsMapForTwelve, 
      PrimeFactorizationAlgorithm.getPrimeFactors(12));

    Map<Integer, Integer> expectedPrimeFactorsMapForEighteen = new HashMap<>();
    expectedPrimeFactorsMapForEighteen.put(2, 1);
    expectedPrimeFactorsMapForEighteen.put(3, 2);

    Assert.assertEquals(expectedPrimeFactorsMapForEighteen, 
      PrimeFactorizationAlgorithm.getPrimeFactors(18));
}

lcm()メソッドは、最初に getPrimeFactors()メソッドを使用して、各数値の素因数分解マップを見つけます。 次に、両方の数値の素因数分解マップを使用して、LCMを見つけます。 このメソッドの反復実装を見てみましょう。

public static int lcm(int number1, int number2) {
    if(number1 == 0 || number2 == 0) {
        return 0;
    }

    Map<Integer, Integer> primeFactorsForNum1 = getPrimeFactors(number1);
    Map<Integer, Integer> primeFactorsForNum2 = getPrimeFactors(number2);

    Set<Integer> primeFactorsUnionSet = new HashSet<>(primeFactorsForNum1.keySet());
    primeFactorsUnionSet.addAll(primeFactorsForNum2.keySet());

    int lcm = 1;

    for (Integer primeFactor : primeFactorsUnionSet) {
        lcm *= Math.pow(primeFactor, 
          Math.max(primeFactorsForNum1.getOrDefault(primeFactor, 0),
            primeFactorsForNum2.getOrDefault(primeFactor, 0)));
    }

    return lcm;
}

良い習慣として、 lcm()メソッドの論理的な正しさを検証します。

@Test
public void testLCM() {
    Assert.assertEquals(36, PrimeFactorizationAlgorithm.lcm(12, 18));
}

4. ユークリッドアルゴリズムの使用

2つの数値のLCMGCD(最大公約数)の間には興味深い関係があり、2つの数値の積の絶対値は彼らのGCDとLCM

前述のように、gcd(a、b)* lcm(a、b)= | a *b|。

したがって、 lcm(a、b)= | a * b | / gcd(a、b)

この式を使用すると、lcm(a、b)を見つけるという元々の問題は、gcd(a、b)を見つけるだけになりました。

確かに、2つの数値のGCDを見つけるには複数の戦略があります。 ただし、ユークリッドアルゴリズムは、すべての中で最も効率的なの1つであることが知られています。

このため、このアルゴリズムの核心を簡単に理解しましょう。これは、次の2つの関係にまとめることができます。

  • gcd(a、b)= gcd(| a%b |、| a |); ここで|a| > = | b |
  • gcd(p、0)= gcd(0、p)= | p |

上記の関係を使用してlcm(12、18)を見つける方法を見てみましょう。

gcd(12、18)= gcd(18%12、12)= gcd(6,12)= gcd(12%6、6)= gcd(0、6)= 6

したがって、lcm(12、18)= | 12 x 18 | / gcd(12、18)=(12 x 18)/ 6 = 36

これで、ユークリッドアルゴリズムの再帰的実装が表示されます。

public static int gcd(int number1, int number2) {
    if (number1 == 0 || number2 == 0) {
        return number1 + number2;
    } else {
        int absNumber1 = Math.abs(number1);
        int absNumber2 = Math.abs(number2);
        int biggerValue = Math.max(absNumber1, absNumber2);
        int smallerValue = Math.min(absNumber1, absNumber2);
        return gcd(biggerValue % smallerValue, smallerValue);
    }
}

上記の実装では、数値の絶対値を使用しています。GCDは、2つの数値を完全に除算する最大の正の整数であるため、負の約数には関心がありません。

これで、上記の実装が期待どおりに機能するかどうかを確認する準備が整いました。

@Test
public void testGCD() {
    Assert.assertEquals(6, EuclideanAlgorithm.gcd(12, 18));
}

4.1. 2つの数値のLCM

以前の方法を使用してGCDを見つけることで、LCMを簡単に計算できるようになりました。 ここでも、 lcm()メソッドは、LCMを返すために2つの整数を入力として受け入れる必要があります。 Javaでこのメソッドを実装する方法を見てみましょう。

public static int lcm(int number1, int number2) {
    if (number1 == 0 || number2 == 0)
        return 0;
    else {
        int gcd = gcd(number1, number2);
        return Math.abs(number1 * number2) / gcd;
    }
}

これで、上記のメソッドの機能を確認できます。

@Test
public void testLCM() {
    Assert.assertEquals(36, EuclideanAlgorithm.lcm(12, 18));
}

4.2. BigIntegerクラスを使用した多数のLCM

大きな数のLCMを計算するには、BigIntegerクラスを利用できます。

内部的には、BigIntegerクラスの gcd()メソッドは、ハイブリッドアルゴリズムを使用して計算パフォーマンスを最適化します。 さらに、 BigIntegerオブジェクトは不変であるため、実装は MutableBigIntegerクラスの可変インスタンスを利用して、頻繁なメモリ再割り当てを回避します。

まず、従来のユークリッドアルゴリズムを使用して、高い方の整数を低い方の整数のモジュラスに繰り返し置き換えます。

その結果、ペアはますます小さくなるだけでなく、連続した除算の後に互いに近づきます最終的に、の大きさを保持するために必要なintの数の違いそれぞれのint[]値配列内の2つのMutableBigIntegerオブジェクトが1または0に達します。

この段階で、戦略はバイナリGCDアルゴリズムに切り替えられ、さらに高速な計算結果が得られます。

この場合も、数値の積の絶対値をGCDで割ってLCMを計算します。 前の例と同様に、 lcm()メソッドは2つの BigInteger 値を入力として受け取り、2つの数値のLCMをBigIntegerとして返します。 実際の動作を見てみましょう。

public static BigInteger lcm(BigInteger number1, BigInteger number2) {
    BigInteger gcd = number1.gcd(number2);
    BigInteger absProduct = number1.multiply(number2).abs();
    return absProduct.divide(gcd);
}

最後に、テストケースでこれを確認できます。

@Test
public void testLCM() {
    BigInteger number1 = new BigInteger("12");
    BigInteger number2 = new BigInteger("18");
    BigInteger expectedLCM = new BigInteger("36");
    Assert.assertEquals(expectedLCM, BigIntegerLCM.lcm(number1, number2));
}

5. 結論

このチュートリアルでは、Javaで2つの数値の最小公倍数を見つけるためのさまざまな方法について説明しました。

さらに、数値の積とLCMおよびGCDとの関係についても学びました。 2つの数値のGCDを効率的に計算できるアルゴリズムを前提として、LCM計算の問題をGCD計算の1つに減らしました。

いつものように、この記事で使用されているJava実装の完全なソースコードは、GitHubで入手できます。