Javaで2つの数値が比較的素かどうかを調べる

1. 概要

_a_と_b_という2つの整数が与えられた場合、両方を分割する唯一の因子が1である場合、それらは*比較的素数であると言います。 互いに素または共素は、比較的素数の同義語です。*
このクイックチュートリアルでは、Javaを使用してこの問題を解決します。

2. 最大共通因子アルゴリズム

結局のところ、2つの数値_a_と_b_の最大公約数(_gcd_)が1の場合(つまり、 _gcd(a、b)= 1_)_a_と_b_は比較的素です。 その結果、2つの数値が比較的素数であるかどうかを判断するには、_gcd_が1であるかどうかを調べるだけです。

3. ユークリッドアルゴリズムの実装

このセクションでは、https://en.wikipedia.org/wiki/Euclidean_algorithm [ユークリッドアルゴリズム]を使用して、2つの数値の_gcd_を計算します。
実装を示す前に、アルゴリズムを要約し、理解のためにそれを適用する方法の簡単な例を見てみましょう。
したがって、_a_と_b_の2つの整数があるとします。 反復アプローチでは、最初に_a_を_b_で除算し、残りを取得します。 次に、_a_に_b_の値を割り当て、_b_に剰余値を割り当てます。 _b_ = _0_になるまでこのプロセスを繰り返します。 最後に、このポイントに到達すると、_a_の値を_gcd_の結果として返します。_a_= _1_の場合、_a_と_b_は比較的素数であると言えます。
__a = 81 __and _b = 35_の2つの整数で試してみましょう。
この場合、__ 81 __and __35(81%35)__is _11_の残り。 したがって、最初の反復ステップでは、_a = 35_および_b = 11_で終了します。 したがって、別の繰り返しを行います。
_35_を__11 _____で割った残りは_2_です。 その結果、_a = 11_(値を交換しました)と_b = 2_になりました。 続けましょう。
もう1つステップを実行すると、_a = 2_および_b = 1_になります。 今、私たちは終わりに近づいています。
最後に、もう一度繰り返した後、__ a = 1 __and _b = 0_に到達します。 アルゴリズムは_1_を返し、__81 __および_35_は実際に比較的素数であると結論付けることができます。

3.1. 命令的な実装

まず、上記のように、ユークリッドアルゴリズムの命令型Javaバージョンを実装しましょう。
int iterativeGCD(int a, int b) {
    int tmp;
    while (b != 0) {
        if (a < b) {
            tmp = a;
            a = b;
            b = tmp;
        }
        tmp = b;
        b = a % b;
        a = tmp;
    }
    return a;
}
気づくように、__a __が_b_より小さい場合、続行する前に値を交換します。 アルゴリズムは、__b __が0のときに停止します。

3.2. 再帰的実装

次に、再帰的な実装を見てみましょう。 これは、明示的な変数値のスワップを回避するため、おそらくよりクリーンです。
int recursiveGCD(int a, int b) {
    if (b == 0) {
        return a;
    }
    if (a < b) {
        return recursiveGCD(b, a);
    }
    return recursiveGCD(b, a % b);
}

4. BigInteger’s実装の使用

しかし、ちょっと待ってください。_gcd_アルゴリズムはすでにJavaに実装されていませんか? はい、そうです! _BigInteger_クラスは、最大公約数を見つけるためのユークリッドアルゴリズムを実装する_gcd_メソッドを提供します。
この方法を使用すると、次のように比較的素数のアルゴリズムをより簡単に作成できます。
boolean bigIntegerRelativelyPrime(int a, int b) {
    return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).equals(BigInteger.ONE);
}

5. 結論

このクイックチュートリアルでは、_gcd_アルゴリズムの3つの実装を使用して、2つの数値が比較的素数であるかどうかを見つける問題の解決策を示しました。
そして、いつものように、サンプルコードが利用可能です。