Gcd java

Hey guys!! Welcome to flower brackets blog. Well, today you will be learning gcd java.

gcd java

GCD and LCM were hard nut to crack in my school days. Well, first let us understand what these terms mean in java??

Greatest Common Divisor(GCD)

Greatest Common Divisor of two integers(or more) is the largest positive integer that divides the numbers without a remainder.

Least Common Multiple(LCM)

Least Common Multiple(lcm java) of two integers a and b is the smallest non zero positive integer that is divisible by both a and b.

Let’s see java program to find the GCD and LCM of two numbers,

Example: gcd java

Also Read – Java Program To Find Even Or Odd

import java.util.Scanner;

public class LCMGCD
{
   static int lcm(int a, int b)
   {
      int x;
      x = (a > b) ? a : b;
      while(true)
      {
         if(x % a == 0 && x % b == 0)
            return x;
            ++x;
      }
   }

   static int gcd(int a, int b)
   {
      int z = 0;
      int p, q;
      p = (a > b) ? a : b;
      q = (a < b) ? a : b;
      z = q;
      while(p % q != 0)
      {
         z = p % q;
         p = q;
         q = z;
      }
      return z;
   }

   public static void main(String[] args)
   {
      Scanner sc = new Scanner(System.in);
      System.out.println("Please enter two numbers: ");
      int a = sc.nextInt();
      int b = sc.nextInt();
      System.out.println("The LCM of two numbers is: " + lcm(a,b));
      System.out.println("The GCD of two numbers is: " + gcd(a,b));
      sc.close();
   }
}

Output:

Please enter two numbers: 15 25
The LCM of two numbers is: 75
The GCD of two numbers is: 5


Java program to find GCD and LCM of two numbers using euclid’s algorithm

Now let’s learn how to find gcd in java using euclid’s method. Here’s the euclid’s algorithm,

GCD = GCD(y, x % y) and GCD(x, 0) = x
x and y are two numbers

Also we can calculate LCM using reduction by GCD,

LCM = x * y / GCD(x, y)
x and y are two numbers

import java.util.Scanner;

public class GCDJava
{
   public static void main(String[] args)
   {
      Scanner sc = new Scanner(System.in);
      System.out.println("Please enter the two numbers : ");
      int numOne = sc.nextInt();
      int numTwo = sc.nextInt();

      System.out.println("GCD of two numbers is: " + findGCD(numOne, numTwo));
      System.out.println("LCM of two numbers is: " + findLCM(numOne, numTwo));
      sc.close();
   }

   // euclid's algorithm for calculating GCD
   public static int findGCD(int x, int y)
   {
      if(y == 0)
         return x;
      else
         return findGCD(y, x % y);
   }

   public static int findLCM(int x, int y)
   {
      return x * y / (findGCD(x, y));
   }
}

Output:

Please enter the two numbers :
8
12
GCD of two numbers is: 4
LCM of two numbers is: 24


Java program to find the GCD of two numbers

Let’s see a new method to find gcd of two numbers in java using successive division method which is less time consuming,

// Method 1 :

import java.util.Scanner;

public class GCDJavaExample
{
   public static void main(String[] args) throws Exception
   {
      Scanner sc = new Scanner(System.in);
      System.out.print("Please enter first number : ");
      int num1 = sc.nextInt();
      System.out.print("Please enter second number : ");
      int num2 = sc.nextInt();
      int temp;
 
      while(num2 != 0)
      {
         temp = num1 % num2;
         num1 = num2;
         num2 = temp;
      }
      System.out.print("The GCD of two numbers is : " + num1);
      sc.close();
   }
}

Output:

Please enter first number : 32
Please enter second number : 23
The GCD of two numbers is : 1

// Method 2 :

import java.util.Scanner;

public class GCDJavaDemo
{
   public static void main(String[] args) throws Exception
   {
      Scanner sc = new Scanner(System.in);
      System.out.print("Please enter first number : ");
      int num1 = sc.nextInt();
      System.out.print("Please enter second number : ");
      int num2 = sc.nextInt();
 
      while(num1 != num2)
      {
         if(num1 > num2)
            num1 = num1 - num2;
         else
            num2 = num2 - num1;
      }
      System.out.print("The GCD of two numbers is : " + num1);
      sc.close();
   }
}

Output:

Please enter first number : 65
Please enter second number : 95
The GCD of two numbers is : 5


Conclusion

That’s it guys. This is all about GCD and LCM of two numbers in java.

I hope you guys have understood the java program. You can subscribe to my blog flower brackets if you haven’t already.

Do share this post if you like.

Related Posts