How to find GCD LCM on a set of numbers

Question

What would be the easiest way to calculate Greatest Common Divisor and Least Common Multiple on a set of numbers  What math functions can be used to find this information

User · Answer

There are no build in function for it  You can find the GCD of two numbers using Euclid s algorithm   For a set of number  GCD a 1 a 2 a 3     a n    GCD  GCD a 1  a 2   a 3  a 4      a n     Apply it recursively   Same for LCM   LCM a b    a   b   GCD a b  LCM a 1 a 2 a 3     a n    LCM  LCM a 1  a 2   a 3  a 4      a n

User · Answer

import java util Scanner  public class Lcmhcf            param args the command line arguments     public static void main String   args           TODO code application logic here     Scanner scan   new Scanner System in       int n1 n2 x y lcm hcf      System out println  Enter any 2 numbers            n1 scan nextInt        n2 scan nextInt        x n1      y n2       do         if n1 gt n2            n1 n1-n2                  else           n2 n2-n1                  while n1  n2        hcf n1       lcm x y hcf       System out println  HCF IS     hcf        System out println  LCM IS     lcm                   Heading   By Rajeev Lochan Sen

User · Answer

There is an Euclid s algorithm for GCD   public int GCF int a  int b        if  b    0  return a      else return  GCF  b  a   b        By the way  a and b should be greater or equal 0  and LCM    ab    GCF a  b

User · Answer

With Java 8  there are more elegant and functional ways to solve this   LCM   private static int lcm int numberOne  int numberTwo        final int bigger   Math max numberOne  numberTwo       final int smaller   Math min numberOne  numberTwo        return IntStream rangeClosed 1 smaller                       filter factor - gt   factor   bigger    smaller    0                       map factor - gt  Math abs factor   bigger                        findFirst                        getAsInt        GCD   private static int gcd int numberOne  int numberTwo        return  numberTwo    0    numberOne   gcd numberTwo  numberOne   numberTwo       Of course if one argument is 0  both methods will not work

User · Answer

Basically to find gcd and lcm on a set of numbers you can use below formula   LCM a  b  X HCF a  b    a   b   Meanwhile in java you can use euclid s algorithm to find gcd and lcm  like this  public static int GCF int a  int b        if  b    0               return a            else              return  GCF b  a   b              You can refer this resource to find examples on euclid s algorithm

User · Answer

int gcf int a  int b        while  a    b     while the two numbers are not equal                         subtract the smaller one from the larger one          if  a  gt  b  a -  b     if a is larger than b  subtract b from a         else b -  a     if b is larger than a  subtract a from b            return a     or return b  a will be equal to b either way    int lcm int a  int b           the lcm is simply  a   b  divided by the gcf of the two      return  a   b    gcf a  b

User · Answer

import java util Scanner  public class Main       public static void main String   args            Scanner input   new Scanner System in           int n0   input nextInt       number of intended input          int    MyList   new int  n0            for  int i   0  i  lt  n0  i                MyList i    input nextInt                  input values stored in an array         int i   0          int count   0              int gcd   1     Initial gcd is 1             int k   2     Possible gcd             while  k  lt   MyList i   amp  amp  k  lt   MyList i                     if  MyList i    k    0  amp  amp  MyList i    k    0                      gcd   k     Update gcd                 k                    count      checking array for gcd                             int i   0              MyList  i    gcd              for  int e  MyList                    System out println e

User · Answer

import java util    public class lcm       public static void main String args                  int lcmresult 1          System out println  Enter the number1              Scanner s new Scanner System in           int a s nextInt            System out println  Enter the number2              int b s nextInt            int max a gt b a b          for int i 2 i lt  max i                          while a i  0  b i  0                                lcmresult lcmresult i                  if a i  0                      a a i                  if b i  0                      b b i                  if a  1 amp  amp b  1                      break                              System out println  lcm    lcmresult

User · Answer

If you can use Java 8  and actually want to  you can use lambda expressions to solve this functionally   private static int gcd int x  int y        return  y    0    x   gcd y  x   y      public static int gcd int    numbers        return Arrays stream numbers  reduce 0   x  y  - gt  gcd x  y       public static int lcm int    numbers        return Arrays stream numbers  reduce 1   x  y  - gt  x    y   gcd x  y         I oriented myself on Jeffrey Hantin s answer  but   calculated the gcd functionally used the varargs-Syntax for an easier API  I was not sure if the overload would work correctly  but it does on my machine  transformed the gcd of the numbers-Array into functional syntax  which is more compact and IMO easier to read  at least if you are used to functional programming    This approach is probably slightly slower due to additional function calls  but that probably won t matter at all for the most use cases

User · Answer

int lcmcal int i int y        int n x s 1 t 1      for n 1  n                  s i n          for x 1 t lt s x                          t y x                    if s  t              break            return s

User · Answer

for gcd you cad do as below       String   ss   new Scanner System in  nextLine   split    s         BigInteger bi bi2   null      bi2   new BigInteger ss 1        for int i   0   i lt ss length-1   i  2                 bi   new BigInteger ss i            bi2   bi gcd bi2             System out println bi2 toString

User · Answer

public class HcfLcm       public static void main String   args            System out println  quot HCF   quot   getHcf 20  15      5         System out println  quot LCM   quot   getLcm2 20  15      60            private static Integer getLcm2 int n1  int n2            int lcm   Math max n1  n2              Always true         while  true                if  lcm   n1    0  amp  amp  lcm   n2    0                    break                              lcm                    return lcm             private static Integer getLcm int i  int j            int hcf   getHcf i  j           return hcf   i hcf   j hcf     i j hcf            private static Integer getHcf int i  int j            while i j    0                int temp   i j              i   j              j   temp                    return j

User · Answer

I ve used Euclid s algorithm to find the greatest common divisor of two numbers  it can be iterated to obtain the GCD of a larger set of numbers   private static long gcd long a  long b        while  b  gt  0                long temp   b          b   a   b       is remainder         a   temp            return a     private static long gcd long   input        long result   input 0       for int i   1  i  lt  input length  i    result   gcd result  input i        return result      Least common multiple is a little trickier  but probably the best approach is reduction by the GCD  which can be similarly iterated   private static long lcm long a  long b        return a    b   gcd a  b       private static long lcm long   input        long result   input 0       for int i   1  i  lt  input length  i    result   lcm result  input i        return result

User · Answer

int lcm   1  int y   0  boolean flag   false  for int i 2 i lt  n i                 if lcm i  0                   for int j i-1 j gt 1 j--                       if i j  0                           flag  true                          y   j                          break                                                          if flag                       lcm   lcm i y                                    else                      lcm   lcm i                                              flag   false              here  first for loop is for getting every numbers starting from  2   then if statement check whether the number i  divides lcm if it does then it skip that no  and if it doesn t then next for loop is for finding a no  which can divides the number i  if this happens we don t need that no  we only wants its extra factor  so here if the flag is true this means there already had some factors of no   i  in lcm  so we divide that factors and multiply the extra factor to lcm  If the number isn t divisible by any of its previous no  then when simply multiply it to the lcm

[java] How to find GCD, LCM on a set of numbers

Examples related to java

Examples related to math

Examples related to greatest-common-divisor

Examples related to lcm