Javaで最小公倍数を見つける

1. 概要

  • https://en.wikipedia.org/wiki/Least_common_multiple [最小公倍数](LCM)の2つの非ゼロ整数_(a、b)_は、_a_と_b_の両方で完全に割り切れる最小の正の整数です。 。*

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

2. 簡単なアルゴリズムを使用した2つの数値のLCMの計算

  • https://en.wikipedia.org/wiki/Multiplication [multiplication]は繰り返し加算*であるという単純な事実を使用して、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などのhttps://docs.oracle.com/javase/8/docs/api/java/lang/Math.html[_Math_]クラスの対応する静的メソッドを使用できます。 ()、_および_max()_、それぞれ。
_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. 素因数分解アプローチの使用

  • https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic [算術の基本定理]は、1より大きいすべての整数を素数の累乗の積として一意に表現することができると述べています。*

    したがって、N> 1の整数の場合、N =(2 ^ k1 ^)*(3 ^ k2 ^)*(5 ^ k3 ^)*…
    この定理の結果を使用して、2つの数値のLCMを見つける素因数分解アプローチを理解します。

* 3.1。 アルゴリズム*

素因数分解アプローチは、https://proofwiki.org/wiki/LCM_from_Prime_Decomposition [2つの数値の素分解からのLCM]を計算します。 素因数分解の素因数と指数を使用して、2つの数値のLCMを計算できます。
とき、| a | =(2 ^ p1 ^)*(3 ^ p2 ^)*(5 ^ p3 ^)*…および| b | =(2 ^ q1 ^)*(3 ^ q2 ^)*(5 ^ q3 ^)*… then、* lcm(a、b)=(2 ^ max(p〜1〜、q〜1〜) ^)*(3 ^ max(p〜2〜、q〜2〜)^)*(5 ^ max(p〜3〜、q〜3〜)^)… *
このアプローチを使用して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実装では、2つの数値の素因数分解表現を使用してLCMを見つけます。
この目的のために、_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. ユークリッドアルゴリズムの使用

https://en.wikipedia.org/wiki/Least_common_multiple[LCM]とhttps://en.wikipedia.org/wiki/Greatest_common_divisor[GCD](Greatest Common Divisor)の間には興味深い関係があります。 https://proofwiki.org/wiki/Product_of_GCD_and_LCM[*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 *を見つけるには複数の戦略があります。 ただし、* https://en.wikipedia.org/wiki/Euclidean_algorithm [ユークリッドアルゴリズム]は、最も効率的なものの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を計算するには、_https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html [BigInteger] _クラスを活用できます。
内部的に、_BigInteger_クラスの* _gcd()_メソッドは、ハイブリッドアルゴリズム*を使用して計算パフォーマンスを最適化します。 さらに、* _ BigInteger_オブジェクトは不変*であるため、実装は* _https://github.com/openjdk/jdk/blob/6bab0f539fba8fb441697846347597b4a0ade428/src/java.base/share/classes/java/math/MutableBigIntegerの可変インスタンスを活用します。 .java [MutableBigInteger] _クラス。頻繁なメモリ再割り当てを回避します*。
*最初に、従来のユークリッドアルゴリズム*を使用して、高い整数をそのモジュラスで低い整数に繰り返し置き換えます。
その結果、ペアは次第に小さくなっていくだけでなく、連続して分割された後に互いに近づきます**。**最終的に、それぞれの_int [で2つの_MutableBigInteger_オブジェクトの大きさを保持するために必要な__int__sの数の差] _値配列は1または0に達します。
この段階で、戦略を* https://en.wikipedia.org/wiki/Binary_GCD_algorithm [Binary 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実装の完全なソースコードは、https://github.com/eugenp/tutorials/tree/master/java-numbers-2 [GitHub]で入手できます。