How to find GCD, LCM for dialing numbers

Question

What would be the easiest way to calculate the Greatest Common Divisor and Less Common Common on a set of numbers? What math functions can I use to find this information?

Answer 1

I used the Euclidean algorithm to find the greatest common divisor of two numbers; this can be repeated to get the GCD of a larger set of numbers.

private static long gcd(long a, long b) { while (b > 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 < input.length; i++) result = gcd(result, input[i]); return result; } 

The smallest common factor is a little more complicated, but probably the best approach is to reduce using GCD , which can be repeated in the same way:

 private static long lcm(long a, long b) { return a * (b / gcd(a, b)); } private static long gcd(long[] input) { long result = input[0]; for(int i = 1; i < input.length; i++) result = lcm(result, input[i]); return result; } 

Answer 2

There is a Euclidean 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 must be greater than or equal to 0 , and LCM = |ab| / GCF(a, b) |ab| / GCF(a, b)

Answer 3

There is no built-in function for it. You can find the GCD of two numbers using the Euclidean algorithm .

For a set of numbers

 GCD(a_1,a_2,a_3,...,a_n) = GCD( GCD(a_1, a_2), a_3, a_4,..., a_n ) 

Apply it recursively.

The 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 ) 

Answer 4

If you can use Java 8 (and really want to), you can use lambda expressions to solve this problem:

 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) -> gcd(x, y)); } public static int lcm(int... numbers) { return Arrays.stream(numbers).reduce(1, (x, y) -> x * (y / gcd(x, y))); } 

I was guided by Jeffrey Hantin answer , but

• computed gcd functionally
• used the varargs syntax for a simpler API (I was not sure if the overload would work correctly, but it works on my machine)
• converted gcd numbers -Array to a functional syntax that is more compact and IMO easier to read (at least if you are used to functional programming)

This approach is probably a bit slower due to extra function calls, but it probably doesn't matter at all for most use cases.

Answer 5

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

Answer 6

 int lcmcal(int i,int y) { int n,x,s=1,t=1; for(n=1;;n++) { s=i*n; for(x=1;t<s;x++) { t=y*x; } if(s==t) break; } return(s); } 

Answer 7

Java 8 has more elegant and functional solutions to this problem.

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 -> (factor * bigger) % smaller == 0) .map(factor -> 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.

Answer 8

Easier to understand:

 { int num1,num2; int m1,m2,r; cout<<"Enter two numbers: "<<endl; cin>>num1>>num2; if(num1>num2) { m1=num1; m2=num2; } else { m1=num2; m2=num1; } while(r!=0) { r=m1%m2; m1=m2; m2=r; } cout<<"result of gcd of two number is "<<m1<<endl; int lcm= (num1*num2)/m1; cout<<"result of lcm of two number is "<<lcm; } 

- See more at: http://www.easycppcodes.com/2015/01/find-gcd-and-lcm-of-two-numbers-using.html#sthash.lAWwqgS5.dpuf

Answer 9

for gcd you do this:

  String[] ss = new Scanner(System.in).nextLine().split("\\s+"); BigInteger bi,bi2 = null; bi2 = new BigInteger(ss[1]); for(int i = 0 ; i<ss.length-1 ; i+=2 ) { bi = new BigInteger(ss[i]); bi2 = bi.gcd(bi2); } System.out.println(bi2.toString()); 

Answer 10

Basically, to find gcd and lcm on a set of numbers, you can use the formula below,

 LCM(a, b) X HCF(a, b) = a * b 

Meanwhile, in java, you can use the Euclidean algorithm to search for 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 to this resource to find examples on the Euclidean algorithm.

Answer 11

 int lcm(int x,int y){ int i=1; while(true){ if(!(x*i)%y) return x*i; i++; } 

Answer 12

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

Answer 13

 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 < 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 <= MyList[i] && k <= MyList[i]) { if (MyList[i] % k == 0 && 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); } } } 

Answer 14

 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>b?a:b; for(int i=2;i<=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&&b==1) break; } } System.out.println("lcm: "+lcmresult); } } 

Answer 15

 int lcm = 1; int y = 0; boolean flag = false; for(int i=2;i<=n;i++){ if(lcm%i!=0){ for(int j=i-1;j>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 the loop, to get each number, starting with "2". then if the if statement checks whether the number (i) will divide lcm, if that happens, then it will skip this. and if this is not so, then the next one for the cycle - no search. which can divide the number (i) if this happens, we do not need it. we need only its additional factor. therefore, here, if the flag is true, it means that there are already some factors not. 'i' in lcm. therefore, we divide these factors and multiply the additional coefficient by lcm. If the number is not divisible by any of its previous no. then when just multiply it by lcm.

Answer 16

 int main() { int n1,n2,num1,num2,rem,gcd,lcm; printf("Enter a number:"); scanf("%d %d",&num1,&num2); num1=n1; num2=n2; while(num2!=0) { rem=num1%num2; num1=num2; num2=rem; } gcd=num1; lcm=(n1*n2)/gcd; printf("Gcd=%d\n",gcd); printf("Lcm=%d\n",lcm); }