java - Java:最大公約数を取得する

Question

BigIntegerそのような関数が、つまり に存在することを見てきましたBigInteger#gcd。int他のタイプ ( 、longまたは)でも動作する Java の他の関数はありますIntegerか? これはjava.lang.Math.gcd（あらゆる種類のオーバーロードで）理にかなっているようですが、そうではありません。他の場所ですか？

---

(この質問を「これを自分で実装するにはどうすればよいか」と混同しないでください!)

Answer 1

私の知る限り、プリミティブ用の組み込みメソッドはありません。しかし、これと同じくらい簡単なことでうまくいくはずです：

public int gcd(int a, int b) {
   if (b==0) return a;
   return gcd(b,a%b);
}

そのようなことに興味がある場合は、1 行にすることもできます。

public int gcd(int a, int b) { return b==0 ? a : gcd(b, a%b); }

両者は同じバイトコードにコンパイルされるため、2 つの間にまったく違いがないことに注意してください。

Answer 2

int と long の場合、プリミティブとして、実際にはそうではありません。整数の場合、誰かが書いた可能性があります。

BigInteger が int、Integer、long、および Long の (数学/関数) スーパーセットであることを考えると、これらの型を使用する必要がある場合は、それらを BigInteger に変換し、GCD を実行して、結果を元に戻します。

private static int gcdThing(int a, int b) {
    BigInteger b1 = BigInteger.valueOf(a);
    BigInteger b2 = BigInteger.valueOf(b);
    BigInteger gcd = b1.gcd(b2);
    return gcd.intValue();
}

Answer 3

または、GCD を計算するためのユークリッド アルゴリズム...

public int egcd(int a, int b) {
    if (a == 0)
        return b;

    while (b != 0) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }

    return a;
}

Answer 4

Jakarta Commons Math はまさにそれです。

ArithmeticUtils.gcd(int p, int q)

Answer 5

Binary GCDアルゴリズムのこの実装を使用できます

public class BinaryGCD {

public static int gcd(int p, int q) {
    if (q == 0) return p;
    if (p == 0) return q;

    // p and q even
    if ((p & 1) == 0 && (q & 1) == 0) return gcd(p >> 1, q >> 1) << 1;

    // p is even, q is odd
    else if ((p & 1) == 0) return gcd(p >> 1, q);

    // p is odd, q is even
    else if ((q & 1) == 0) return gcd(p, q >> 1);

    // p and q odd, p >= q
    else if (p >= q) return gcd((p-q) >> 1, q);

    // p and q odd, p < q
    else return gcd(p, (q-p) >> 1);
}

public static void main(String[] args) {
    int p = Integer.parseInt(args[0]);
    int q = Integer.parseInt(args[1]);
    System.out.println("gcd(" + p + ", " + q + ") = " + gcd(p, q));
}

}

http://introcs.cs.princeton.edu/java/23recursion/BinaryGCD.java.htmlから

Answer 6

ここでのいくつかの実装は、両方の数値が負の場合、正しく機能しません。gcd(-12, -18) は -6 ではなく 6 です。

したがって、次のような絶対値を返す必要があります

public static int gcd(int a, int b) {
    if (b == 0) {
        return Math.abs(a);
    }
    return gcd(b, a % b);
}

Answer 7

Java 1.5 以降を使用している場合、これはInteger.numberOfTrailingZeros()必要なチェックと反復の数を減らすために使用する反復バイナリ GCD アルゴリズムです。

public class Utils {
    public static final int gcd( int a, int b ){
        // Deal with the degenerate case where values are Integer.MIN_VALUE
        // since -Integer.MIN_VALUE = Integer.MAX_VALUE+1
        if ( a == Integer.MIN_VALUE )
        {
            if ( b == Integer.MIN_VALUE )
                throw new IllegalArgumentException( "gcd() is greater than Integer.MAX_VALUE" );
            return 1 << Integer.numberOfTrailingZeros( Math.abs(b) );
        }
        if ( b == Integer.MIN_VALUE )
            return 1 << Integer.numberOfTrailingZeros( Math.abs(a) );

        a = Math.abs(a);
        b = Math.abs(b);
        if ( a == 0 ) return b;
        if ( b == 0 ) return a;
        int factorsOfTwoInA = Integer.numberOfTrailingZeros(a),
            factorsOfTwoInB = Integer.numberOfTrailingZeros(b),
            commonFactorsOfTwo = Math.min(factorsOfTwoInA,factorsOfTwoInB);
        a >>= factorsOfTwoInA;
        b >>= factorsOfTwoInB;
        while(a != b){
            if ( a > b ) {
                a = (a - b);
                a >>= Integer.numberOfTrailingZeros( a );
            } else {
                b = (b - a);
                b >>= Integer.numberOfTrailingZeros( b );
            }
        }
        return a << commonFactorsOfTwo;
    }
}

単体テスト：

import java.math.BigInteger;
import org.junit.Test;
import static org.junit.Assert.*;

public class UtilsTest {
    @Test
    public void gcdUpToOneThousand(){
        for ( int x = -1000; x <= 1000; ++x )
            for ( int y = -1000; y <= 1000; ++y )
            {
                int gcd = Utils.gcd(x, y);
                int expected = BigInteger.valueOf(x).gcd(BigInteger.valueOf(y)).intValue();
                assertEquals( expected, gcd );
            }
    }

    @Test
    public void gcdMinValue(){
        for ( int x = 0; x < Integer.SIZE-1; x++ ){
            int gcd = Utils.gcd(Integer.MIN_VALUE,1<<x);
            int expected = BigInteger.valueOf(Integer.MIN_VALUE).gcd(BigInteger.valueOf(1<<x)).intValue();
            assertEquals( expected, gcd );
        }
    }
}

Answer 8

他の場所ですか？

アパッチ！- gcd と lcm の両方があり、とてもクールです!

ただし、その実装の深さにより、単純な手書きバージョンに比べて遅くなります (問題がある場合)。

Answer 9

私は14歳の時に作ったこの方法を使いました。

    public static int gcd (int a, int b) {
        int s = 1;
        int ia = Math.abs(a);//<-- turns to absolute value
        int ib = Math.abs(b);
        if (a == b) {
            s = a;
        }else {
            while (ib != ia) {
                if (ib > ia) {
                    s = ib - ia;
                    ib = s;
                }else { 
                    s = ia - ib;
                    ia = s;
                }
            }
        }
        return s;
    }

Answer 10

2 つの数値の間の gcd を与える % は、次のことを意味します: - % または big_number/small_number の mod は =gcd であり、Java で次のように記述し big_number % small_numberます。

EX1: 2 つの整数の場合

  public static int gcd(int x1,int x2)
    {
        if(x1>x2)
        {
           if(x2!=0)
           {
               if(x1%x2==0)     
                   return x2;
                   return x1%x2;
                   }
           return x1;
           }
          else if(x1!=0)
          {
              if(x2%x1==0)
                  return x1;
                  return x2%x1;
                  }
        return x2;
        } 

EX2: 3 つの整数の場合

public static int gcd(int x1,int x2,int x3)
{

    int m,t;
    if(x1>x2)
        t=x1;
    t=x2;
    if(t>x3)
        m=t;
    m=x3;
    for(int i=m;i>=1;i--)
    {
        if(x1%i==0 && x2%i==0 && x3%i==0)
        {
            return i;
        }
    }
    return 1;
}