Javaで最大公約数を見つける

投稿日: 2019-10-18 2022-11-10
タグ: Algorithms, Java

1. 概要

数学では、ゼロ以外の2つの整数の GCD は、各整数を均等に分割する最大の正の整数です。

このチュートリアルでは、2つの整数の最大公約数（GCD）を見つけるための3つのアプローチを見ていきます。さらに、Javaでの実装を見ていきます。

2. 強引な

最初のアプローチでは、1から指定された最小数まで反復し、指定された整数がインデックスで割り切れるかどうかを確認します。 指定された数値を分割する最大のインデックスは、指定された数値のGCDです。

int gcdByBruteForce(int n1, int n2) {
    int gcd = 1;
    for (int i = 1; i <= n1 && i <= n2; i++) {
        if (n1 % i == 0 && n2 % i == 0) {
            gcd = i;
        }
    }
    return gcd;
}

ご覧のとおり、上記の実装の複雑さは O（min（n1、n2））です。これは、ループを n 回繰り返す必要があるためです（小さい数に相当します）。）GCDを検索します。

3. ユークリッドの互除法

次に、ユークリッドのアルゴリズムを使用してGCDを見つけることができます。ユークリッドのアルゴリズムは、効率的であるだけでなく、Javaの再帰を使用して理解しやすく実装しやすいものです。

ユークリッドの方法は、2つの重要な定理に依存しています。

まず、大きい数から小さい数を引いても、GCDは変化しません。したがって、したがって、数を引い続けると、最終的にGCDになります。
第二に、小さい数が大きい数を正確に除算するとき、小さい数は与えられた2つの数のGCDです。

基本的に一度に多くの減算があるため、実装では減算の代わりにモジュロを使用することに注意してください。

int gcdByEuclidsAlgorithm(int n1, int n2) {
    if (n2 == 0) {
        return n1;
    }
    return gcdByEuclidsAlgorithm(n2, n1 % n2);
}

また、n1の位置でn2を使用し、アルゴリズムの再帰ステップで残りをn2の位置で使用する方法にも注意してください。

さらに、ユークリッドのアルゴリズムの複雑さはO（Log min（n1、n2））であり、これは前に見たブルートフォース法と比較して優れています。

4. スタインのアルゴリズムまたはバイナリGCDアルゴリズム

最後に、Steinのアルゴリズム（バイナリGCDアルゴリズムとしても知られる）を使用して、2つの非負の整数のGCDを見つけることができます。このアルゴリズムは、算術シフト、比較、減算などの単純な算術演算を使用します。

Steinのアルゴリズムは、GCDに関連する次の基本IDを繰り返し適用して、2つの非負の整数のGCDを見つけます。

gcd（0、0）= 0、gcd（n1、0）= n1、gcd（0、n2）= n2
n1とn2が両方とも偶数の整数の場合、 gcd（n1、n2）= 2 * gcd（n1 / 2、n2 / 2）、2公約数です
n1 が偶数の整数で、 n2 が奇数の整数の場合、 gcd（n1、n2）= gcd（n1 / 2、n2）、2はそうではないため最大公約数およびその逆
n1とn2が両方とも奇数の整数であり、 n1> = n2 の場合、 gcd（n1、n2）= gcd（（n1-n2 ）/ 2、n2）およびその逆

n1がn2、または n1 = 0 になるまで、手順2〜4を繰り返します。 GCDは（2n）*n2です。ここで、 n は、ステップ2の実行中にn1とn2で2が共通して検出された回数です。

int gcdBySteinsAlgorithm(int n1, int n2) {
    if (n1 == 0) {
        return n2;
    }

    if (n2 == 0) {
        return n1;
    }

    int n;
    for (n = 0; ((n1 | n2) & 1) == 0; n++) {
        n1 >>= 1;
        n2 >>= 1;
    }

    while ((n1 & 1) == 0) {
        n1 >>= 1;
    }

    do {
        while ((n2 & 1) == 0) {
            n2 >>= 1;
        }

        if (n1 > n2) {
            int temp = n1;
            n1 = n2;
            n2 = temp;
        }
        n2 = (n2 - n1);
    } while (n2 != 0);
    return n1 << n;
}

2で除算または乗算するために算術シフト演算を使用していることがわかります。さらに、与えられた数を減らすために減算を使用します。

n1> n2がO（（log2n1）2）である場合の、スタインのアルゴリズムの複雑さ。いつ n1 それは O（（log2n2）2）。

5. 結論

このチュートリアルでは、2つの数値のGCDを計算するためのさまざまな方法について説明しました。また、これらをJavaで実装し、それらの複雑さを簡単に確認しました。

いつものように、ここでの例の完全なソースコードは、いつものように、GitHub上にあります。

getdocs

13036