Java get greatest common divisor

Question

I have seen that such a function exists for BigInteger  i e  BigInteger gcd  Are there other functions in Java which also work for other types  int  long or Integer   It seems this would make sense as java lang Math gcd  with all kinds of overloads  but it is not there  Is it somewhere else      Don t confuse this question with  how do I implement this myself   please

User · Answer

Use Guava LongMath gcd   and IntMath gcd

User · Answer

public int gcd int num1  int num2         int max   Math abs num1       int min   Math abs num2        while  max  gt  0            if  max  lt  min                int x   max              max   min              min   x                    max    min             return min      This method uses the Euclid   s algorithm to get the  Greatest Common Divisor  of two integers  It receives two integers and returns the gcd of them  just that easy

User · Answer

we can use recursive function for find 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  gt  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

User · Answer

You can use this implementation of Binary GCD algorithm  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  amp  1     0  amp  amp   q  amp  1     0  return gcd p  gt  gt  1  q  gt  gt  1   lt  lt  1          p is even  q is odd     else if   p  amp  1     0  return gcd p  gt  gt  1  q           p is odd  q is even     else if   q  amp  1     0  return gcd p  q  gt  gt  1           p and q odd  p  gt   q     else if  p  gt   q  return gcd  p-q   gt  gt  1  q           p and q odd  p  lt  q     else return gcd p   q-p   gt  gt  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           From http   introcs cs princeton edu java 23recursion BinaryGCD java html

User · Answer

Some implementations here are not working correctly if both numbers are negative  gcd -12  -18  is 6  not -6   So an absolute value should be returned  something like  public static int gcd int a  int b        if  b    0            return Math abs a             return gcd b  a   b

User · Answer

I used this method that I created when I was 14 years old       public static int gcd  int a  int b            int s   1          int ia   Math abs a     lt -- turns to absolute value         int ib   Math abs b           if  a    b                s   a           else               while  ib    ia                    if  ib  gt  ia                        s   ib - ia                      ib   s                   else                        s   ia - ib                      ia   s                                                    return s

User · Answer

Unless I have Guava  I define like this   int gcd int a  int b      return a    0   b   gcd b   a  a

User · Answer

Or the Euclidean algorithm for calculating the GCD     public int egcd int a  int b        if  a    0          return b       while  b    0            if  a  gt  b              a   a - b          else             b   b - a             return a

User · Answer

Is it somewhere else    Apache  - it has both gcd and lcm  so cool   However  due to profoundness of their implementation  it s slower compared to simple hand-written version  if it matters

User · Answer

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  gt  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

User · Answer

The   going to give us the gcd Between two numbers  it means -   or mod of big number small number are  gcd  and we write it on java like this  big number   small number   EX1  for two integers    public static int gcd int x1 int x2                if x1 gt 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  for three integers  public static int gcd int x1 int x2 int x3         int m t      if x1 gt x2          t x1      t x2      if t gt x3          m t      m x3      for int i m i gt  1 i--                if x1 i  0  amp  amp  x2 i  0  amp  amp  x3 i  0                        return i                      return 1

User · Answer

Jakarta Commons Math has exactly that   ArithmeticUtils gcd int p  int q

User · Answer

As far as I know  there isn t any built-in method for primitives  But something as simple as this should do the trick   public int gcd int a  int b       if  b  0  return a     return gcd b a b       You can also one-line it if you re into that sort of thing   public int gcd int a  int b    return b  0   a   gcd b  a b       It should be noted that there is absolutely no difference between the two as they compile to the same byte code

User · Answer

For int and long  as primitives  not really   For Integer  it is possible someone wrote one   Given that BigInteger is a  mathematical functional  superset of int  Integer  long  and Long  if you need to use these types  convert them to a BigInteger  do the GCD  and convert the result back   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

User · Answer

Those GCD functions provided by Commons-Math and Guava have some differences    Commons-Math throws an ArithematicException class only for Integer MIN VALUE or Long MIN VALUE    Otherwise  handles the value as an absolute value   Guava throws an IllegalArgumentException class for any negative values

User · Answer

If you are using Java 1 5 or later then this is an iterative binary GCD algorithm which uses Integer numberOfTrailingZeros   to reduce the number of checks and iterations required   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  lt  lt  Integer numberOfTrailingZeros  Math abs b                       if   b    Integer MIN VALUE               return 1  lt  lt  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  gt  gt   factorsOfTwoInA          b  gt  gt   factorsOfTwoInB          while a    b               if   a  gt  b                     a    a - b                   a  gt  gt   Integer numberOfTrailingZeros  a                  else                   b    b - a                   b  gt  gt   Integer numberOfTrailingZeros  b                                    return a  lt  lt  commonFactorsOfTwo            Unit test   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  lt   1000    x               for   int y   -1000  y  lt   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  lt  Integer SIZE-1  x                  int gcd   Utils gcd Integer MIN VALUE 1 lt  lt x               int expected   BigInteger valueOf Integer MIN VALUE  gcd BigInteger valueOf 1 lt  lt x   intValue                assertEquals  expected  gcd

[java] Java: get greatest common divisor

Examples related to java

Examples related to greatest-common-divisor