2つの数値がJavaで互いに素であるかどうかを調べる

投稿日: 2019-10-19 2022-11-05
タグ: Algorithms, Java, Math

1. 概要

2つの整数が与えられると、 a と b 、私たちは彼らが両方を分割する唯一の要因が1である場合、互いに素です。互いに素または互いに素は、比較的素数の同義語です。

このクイックチュートリアルでは、Javaを使用してこの問題の解決策を説明します。

2. 最大公約数アルゴリズム

結局のところ、2つの数aとbの最大公約数（ gcd ）が1（つまり gcd（a、b）= 1 ）の場合、aとbは互いに素です。結果として、2つの数が互いに素であるかどうかを判断することは、gcdが1であるかどうかを見つけることだけで構成されます。

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

このセクションでは、ユークリッドアルゴリズムを使用して、2つの数値のgcdを計算します。

実装を示す前に、アルゴリズムを要約し、理解のためにそれを適用する方法の簡単な例を見てみましょう。

したがって、aとbの2つの整数があると想像してください。反復アプローチでは、最初にaをbで除算し、余りを取得します。次に、aにbの値を割り当て、bに余りの値を割り当てます。 b = 0になるまでこのプロセスを繰り返します。最後に、このポイントに到達すると、aの値をgcdの結果として返し、 a = 1 の場合、次のようになります。 aとbは互いに素であると言えます。

a =81とb=35の2つの整数で試してみましょう。

この場合、 81と35（81％35）の残りは11です。したがって、最初の反復ステップでは、 a =35およびb=11で終了します。したがって、別の反復を行います。

35を11で割った余りは2です。その結果、 a = 11 （値を交換）および b =2になりました。続けましょう。

もう1つのステップは、 a =2およびb=1になります。今、私たちは終わりに近づいています。

最後に、もう一度繰り返した後、 a =1および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の実装の使用

しかし、待ってください— 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つの数が互いに素であるかどうかを見つける問題の解決策を示しました。

また、いつものように、サンプルコードはGitHubでから入手できます。

getdocs

13036