Java: uzyskaj największy wspólny dzielnik

Widziałem, że taka funkcja istnieje BigIntegernp BigInteger#gcd. Czy istnieją inne funkcje w Javie, które również praca dla innych typów ( int, longlub Integer)? Wydaje się, że miałoby to sens java.lang.Math.gcd(przy wszelkiego rodzaju przeciążeniach), ale go tam nie ma. Czy to gdzieś indziej?

(Nie myl tego pytania z „jak mam to zaimplementować”, proszę!)

Przez długi czas, jak prymitywy, nie do końca. Dla Integera jest możliwe, że ktoś taki napisał.

Biorąc pod uwagę, że BigInteger jest (matematycznym / funkcjonalnym) nadzbiorem int, Integer, long i Long, jeśli chcesz użyć tych typów, przekonwertuj je na BigInteger, wykonaj GCD i przekonwertuj wynik z powrotem.

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

O ile wiem, nie ma żadnej wbudowanej metody dla prymitywów. Ale coś tak prostego powinno załatwić sprawę:

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

Możesz również wpisać jedną linijkę, jeśli lubisz takie rzeczy:

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

Należy zauważyć, że nie ma absolutnie żadnej różnicy między nimi, ponieważ kompilują się do tego samego kodu bajtowego.

Albo algorytm euklidesowy do obliczania 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;
}

Użyj guawy LongMath.gcd()iIntMath.gcd()

O ile nie mam guawy, definiuję w ten sposób:

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

Jakarta Commons Math właśnie to ma.

ArithmeticUtils.gcd (int p, int q)

Możesz użyć tej implementacji algorytmu binarnego 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));
}

}

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

Niektóre implementacje tutaj nie działają poprawnie, jeśli obie liczby są ujemne. gcd (-12, -18) to 6, a nie -6.

Powinna więc zostać zwrócona wartość bezwzględna, coś w rodzaju

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

możemy użyć funkcji rekurencyjnej do znalezienia 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));
    }
}

Jeśli używasz języka Java 1.5 lub nowszego, jest to iteracyjny binarny algorytm GCD, który używa Integer.numberOfTrailingZeros()do zmniejszenia liczby wymaganych sprawdzeń i iteracji.

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

Test jednostkowy:

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

public int gcd(int num1, int num2) { 
    int max = Math.abs(num1);
    int min = Math.abs(num2);

    while (max > 0) {
        if (max < min) {
            int x = max;
            max = min;
            min = x;
        }
        max %= min;
    }

    return min;
}

Ta metoda wykorzystuje algorytm Euclid do uzyskania „największego wspólnego dzielnika” dwóch liczb całkowitych. Otrzymuje dwie liczby całkowite i zwraca ich gcd. po prostu takie proste!

Czy to gdzieś indziej?

Apache!- ma zarówno gcd, jak i lcm, super!

Jednak ze względu na głębię ich implementacji jest wolniejszy w porównaniu z prostą wersją odręczną (jeśli ma to znaczenie).

/*
import scanner and instantiate scanner class;
declare your method with two parameters
declare a third variable;
set condition;
swap the parameter values if condition is met;
set second conditon based on result of first condition;
divide and assign remainder to the third variable;
swap the result;
in the main method, allow for user input;
Call the method;

*/
public class gcf {
    public static void main (String[]args){//start of main method
        Scanner input = new Scanner (System.in);//allow for user input
        System.out.println("Please enter the first integer: ");//prompt
        int a = input.nextInt();//initial user input
        System.out.println("Please enter a second interger: ");//prompt
        int b = input.nextInt();//second user input


       Divide(a,b);//call method
    }
   public static void Divide(int a, int b) {//start of your method

    int temp;
    // making a greater than b
    if (b > a) {
         temp = a;
         a = b;
         b = temp;
    }

    while (b !=0) {
        // gcd of b and a%b
        temp = a%b;
        // always make a greater than b
        a =b;
        b =temp;

    }
    System.out.println(a);//print to console
  }
}

Użyłem tej metody, którą stworzyłem, gdy miałem 14 lat.

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

Te funkcje GCD dostarczane przez Commons-Math i Guava mają pewne różnice.

• Commons-Math rzuca ArithematicException.classtylko dla Integer.MIN_VALUElub Long.MIN_VALUE.
  • W przeciwnym razie traktuje wartość jako wartość bezwzględną.
• Guawa rzuca znak IllegalArgumentException.classdla wszelkich wartości ujemnych.

% Daje nam gcd Pomiędzy dwiema liczbami oznacza to: -% lub mod z big_number / small_number to = gcd i piszemy to w javie w ten sposób big_number % small_number.

EX1: dla dwóch liczb całkowitych

  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: dla trzech liczb całkowitych

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