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.

Example: gcd java

Let’s see how to find gcd of two numbers java and gcd program in 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


Euclid’s method

Now let’s learn how to find gcd in java using euclid’s method.

import java.util.Scanner;

public class GCDJava
{
   public static void main(String[] args)
   {
      Scanner sc = new Scanner(System.in); 
      System.out.println("Please enter first number : ");
      int num1 = sc.nextInt(); 
      System.out.println("Please enter second number : ");
      int num2 = sc.nextInt();
      System.out.println("The GCD of two numbers is " + num1 + " and " + num2 + " is : " + calculateGCD(num1,num2));
      sc.close();
   }
 
   private static int calculateGCD(int number1, int number2)
   {
      if(number2 == 0)
      {
         return number1;
      } 
      return calculateGCD(number2, number1 % number2);
   }
}

Output:

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


Successive division method

Let’s see a new method to find gcd 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 program to find gcd of two numbers in java and java least common multiple.

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