Java: получить наибольший общий делитель

Question

Я видел, что такая функция существует для BigInteger, т.е. BigInteger#gcd. Существуют ли другие функции в Java, которые также работают для других типов (int, long или Integer)? Кажется, это имеет смысл как java.lang.Math.gcd (со всеми видами перегрузок), но его там нет. Это где-то еще?

---

(Не путайте этот вопрос с вопросом "как мне это реализовать самостоятельно, пожалуйста!)

Answer 1

Насколько я знаю, для примитивов нет встроенного метода.Но что-то такое простое, как это, должно сработать:

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

Вы также можете однострочно, если вам нравится такая вещь:

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

Следует отметитьчто существует абсолютно нет различий между ними, поскольку они компилируются в один и тот же байт-код.

Answer 2

Для int и long, как для примитивов, не совсем. Для Integer, возможно, кто-то написал один.

Учитывая, что 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

Использование гуавы LongMath.gcd() и IntMath.gcd()

Answer 5

Jakarta Commons Math имеет именно это.

ArithmeticUtils.gcd (int p, int q)

Answer 6

Если у меня нет гуавы, я определяю так:

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

Answer 7

Вы можете использовать эту реализацию Двоичный алгоритм 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 8

Некоторые реализации здесь работают неправильно, если оба числа отрицательны. 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 9

мы можем использовать рекурсивную функцию для поиска gcd

public class Test
{
 static int gcd(int a, int b)
    {
        // Everything divides 0 
        if (a == 0 || b == 0)
           return 0;

        // base case
        if (a == b)
            return a;

        // a is greater
        if (a > b)
            return gcd(a-b, b);
        return gcd(a, b-a);
    }

    // Driver method
    public static void main(String[] args) 
    {
        int a = 98, b = 56;
        System.out.println("GCD of " + a +" and " + b + " is " + gcd(a, b));
    }
}

Answer 10

Если вы используете Java 1.5 или более позднюю версию, то это итеративный двоичный алгоритм GCD, который использует Integer.numberOfTrailingZeros() для уменьшения количества необходимых проверок и итераций.

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 );
        }
    }
}