[java] 자바 : 최대 공약수 얻기

Program / 글쓴이

나는 그런 기능이 존재 함을 알 한 BigInteger예 BigInteger#gcd. 다른 유형 ( int, long또는 Integer) 에서도 작동하는 Java에 다른 기능이 있습니까? 이것은 java.lang.Math.gcd(모든 종류의 과부하와 함께) 이해가 될 것 같지만 거기에는 없습니다. 다른 곳에 있습니까?

(이 질문을 “내가 직접 구현하는 방법”과 혼동하지 마십시오!)

답변

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

답변

내가 아는 한, 프리미티브에 대한 내장 메소드는 없습니다. 그러나 이렇게 간단한 것이 트릭을 수행해야합니다.

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

동일한 바이트 코드로 컴파일하기 때문에 둘 사이에는 전혀 차이가 없다는 점에 유의해야합니다 .

답변

또는 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;
}

답변

구아바 LongMath.gcd()와IntMath.gcd()

답변

구아바가 없으면 다음과 같이 정의합니다.

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

답변

Jakarta Commons Math는 정확히 그것을 가지고 있습니다.

ArithmeticUtils.gcd (int p, int q)

답변

이 바이너리 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