Saturday, May 14, 2022

How to Find Greatest Common Divisor of two numbers in Java - [ Euclid's algorithm GCD Example]

How to find the Greatest Common Divisor of two numbers in Java
Simple Java program to find GCD (Greatest Common Divisor) or GCF  (Greatest Common Factor) or HCF (Highest common factor). The GCD of two numbers is the largest positive integer that divides both the numbers fully i.e. without any remainder. There are multiple methods to find GCD, GDF, or HCF of two numbers but  Euclid's algorithm is very popular and easy to understand, of course, only if you understand how recursion works. Euclid's algorithm is an efficient way to find the GCD of two numbers and it's pretty easy to implement using recursion in the Java program. According to Euclid's method GCD of two numbers, a, b is equal to GCD(b, a mod b) and GCD(a, 0) = a.

The latter case is the base case of our Java program to find the GCD of two numbers using recursion. You can also calculate the greatest common divisor in Java without using recursion but that would not be as easy as the recursive version, but still a good exercise from the coding interview point of view.

It's very easy to understand this algorithm once you look at the flow chart, which explains how Euclid's GCD algorithm works. You can also read Introduction to Algorithms book by Thomas Cormen to learn more about similar computer algorithms.

This is one of the most popular books to learn Data structure and algorithms and widely used as textbooks for algorithms in many schools, colleges, and universities. It is also popularly known as CLRS (Cormen, Leiserson, Rivest, Stein).

And, if you need a course then I highly recommend checking out Data Structures and Algorithms: Deep Dive Using Java course on Udemy. It's a hands-on course and covers all essential data structures and perfect for Java developers. 





GCD [Greatest Common Divisor] of Two Integers in Java

In Euclid's algorithm, we start with two numbers X and Y. If Y is zero then the greatest common divisor of both will be X, but if Y is not zero then we assign the Y to X and Y becomes X%Y. Once again we check if Y is zero, if yes then we have our greatest common divisor or GCD otherwise we keep continue like this until Y becomes zero.

Since we are using the modulo operator, the number is getting smaller and smaller at each iteration, so the X%Y will eventually become zero.

Let' take an example of calculating GCD of 54 and 24 using Euclid's algorithm. Here X = 54 and Y = 24 since Y is not zero we move to the logical part and assign X = Y, which means X becomes 24 and Y becomes 54%24 i.e 6.

Since Y is still not zero, we again apply the logic. This time X will become 6 and Y will become 24%6 i.e. Y=0. Bingo, Y is now zero which means we have our answer and it's nothing but the value of X which is 6 (six).

The algorithm will become clearer when you see the flow chart of calculating the GCD of two numbers using recursion as shown below. You can see we are starting with two numbers X and Y and if Y=0 then we got our answer, otherwise, we apply logic and check again.

Now let's learn how to convert Euclid's algorithm to find GCD into Java code.

Euclid's algorithm to find GCD of two numbers in Java


Here is my complete code example of how to find the GCD of two numbers in Java. This Java program uses Euclid's method to find the GCD of two numbers. They must be an integer, so make sure you check the numbers entered by the user like floating-point numbers are not allowed.

Similarly, any alphabets and other characters are not allowed except the '+' and '-' sign, and all these rules are ensured by Scanner.nextInt() call. This method will throw an error if the user will enter an invalid value instead of an integer.

Btw, if you are new to Java and want to learn more about these utility classes like Scanner then I suggest you check out a comprehensive Java course like The Complete Java Masterclass by Tim Buchalaka on Udemy. It's also the most up-to-date course and covers new features from recent Java releases.

How to Find Greatest Common Divisor of two numbers in Java -  [ Euclid's algorithm GCD Example]




Java Program to calculate GCD of two numbers

/**
 * Java program to demonstrate How to find Greatest Common Divisor or GCD of 
 * two numbers using Euclid’s method. There are other methods as well to 
 * find GCD of two number in Java but this example of finding GCD of two number
 * is most simple.
 *
 * @author Javin Paul
 */
public class GCDExample {
  
    public static void main(String args[]){
     
        //Enter two number whose GCD needs to be calculated.      
        Scanner scanner = new Scanner(System.in);
        System.out.println("Please enter first number to find GCD");
        int number1 = scanner.nextInt();
        System.out.println("Please enter second number to find GCD");
        int number2 = scanner.nextInt();
      
        System.out.println("GCD of two numbers " + number1 +" and " 
                           + number2 +" is :" + findGCD(number1,number2));
      
      
    }

    /*
     * Java method to find GCD of two number using Euclid's method
     * @return GDC of two numbers in Java
     */
    private static int findGCD(int number1, int number2) {
        //base case
        if(number2 == 0){
            return number1;
        }
        return findGCD(number2, number1%number2);
    }
  
}

Output:
Please enter first number to find GCD
54
Please enter second number to find GCD
24
GCD of two numbers 54 and 24 is :6


That’s all on how to find the GCD of two numbers in Java. You can use this Java program to prepare for viva or other computer homework and assignment test or for your self-practice to improve programming in Java. 

By the way, there is a couple of other techniques to find Greatest common divisor in Java, as an exercise you can explore those methods and write code for that. The key point is you need to learn how to convert an algorithm into code to become a programmer.

If you like this little programming exercise and hungry for more to improve your coding skill, check out these exercises, they will help to build your programming logic :
  • How to reverse String in Java without using API methods? (Solution)
  • Write a function to find the middle element of the linked list in one pass? (solution)
  • How to check if a number is binary in Java? (answer)
  • 10 Free Data Structure and Algorithms Courses for Beginners (courses)
  • Write a Program to Check if a number is Power of Two or not? (program)
  • 10 Books to learn Data Structure and Algorithms in-depth (books)
  • Write a method to check if two String are Anagram of each other? (method)
  • 100+ data structure and algorithms interview questions (questions)
  • Write a program to check if a number is Prime or not? (solution)
  • Top 5 Courses to learn Data Structure and Algorithms (courses)
  • Write a Program to remove duplicates from an array without using Collection API? (program)
  • 5 Essential Skills to Crack any Coding interview (skills)
  • Write a method to count occurrences of a character in String? (Solution)
  • How to find the Fibonacci sequence up to a given number? (solution)
  • 10 Courses to Crack any Programming interview (courses)
  • How to check if LinkedList contains any cycle in Java? (solution)
  • How to check if a number is Armstrong's number or not? (solution)
  • How do find the largest and smallest number in an array? (solution)
  • Write a method to remove duplicates from ArrayList in Java? (Solution)
  • How to solve the Producer-Consumer Problem in Java. (solution)
  • How to find prime factors of an integer in Java? (solution)
  • Write a program to find the first non-repeated characters from String in Java? (program)

Thanks for reading this article so far. If you like this coding problem and my solution then please share it with your friends and colleagues. If you have any questions or doubt then please let us know and I'll try to find an answer for you. As always suggestions, comments, innovative and better answers are most welcome.


P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check the Data Structure in Java free course on Udemy. It's completely free and all you need to do is create a free Udemy account to enroll in this course. 

26 comments:

  1. Can you also share program to find LCD for numbers in Java? I understand calculating GCD using Euclid's method, but don't find any short trick for calculating LCD similarly. Please help

    ReplyDelete
  2. What is the other way of calculating GCD in Java program, apart from Euclid's method, a comparison would be nice.

    ReplyDelete
    Replies
    1. static int greatestDivisor(int x, int y){
      //create list to show what x and y can be divided with
      ArrayList divisorsList = new ArrayList<>();
      int divisor = 1;

      //loop till both cannot be divided further
      while(x/divisor > 0 || y/divisor > 0){
      if(x%divisor == 0 && y%divisor==0){
      divisorsList.add(divisor);
      }
      divisor++;
      }

      //printing out list of all common divisors
      // for(int div: divisorsList){
      // System.out.println(div);
      // }

      //last added divisor is the greatest common divisor
      return divisorsList.get(divisorsList.size()-1);

      }

      Delete
  3. private static int findlcm(int number1, int number2) {
    int lcm=0;
    for(int i=1;i<=number2;i++){
    lcm=number1*i;
    if(lcm%number2==0){
    break;
    }
    }
    return lcm;
    }

    ReplyDelete
    Replies
    1. i built a program w/c is suppose to calculate GCD and LCD but i dont know where to insert its formula??
      here is my code..

      import java.awt.*;
      import java.awt.event.*;
      import javax.swing.*;

      public class Distruc extends JFrame implements ActionListener{

      Container con;
      JLabel lbl1,lbl2,lbl3;
      JTextField txt1,txt2,txt3;
      JButton btn1,btn2,btn3;

      public Distruc(){
      con = getContentPane();
      con.setLayout(new FlowLayout());

      txt1 = new JTextField(10);
      txt2 = new JTextField(10);
      txt3 = new JTextField(10);

      lbl1 = new JLabel("INPUT 1: ");
      lbl2 = new JLabel("INPUT 2: ");
      lbl3 = new JLabel("RESULT: ");

      btn1 = new JButton("GCD");
      btn1.addActionListener(this);
      btn2 = new JButton("LCD");
      btn2.addActionListener(this);
      btn3 = new JButton("DONE");
      btn3.addActionListener(this);

      txt1.setText("");
      txt2.setText("");
      txt3.setText("");

      con.add(lbl1);
      con.add(txt1);
      con.add(lbl2);
      con.add(txt2);
      con.add(btn1);
      con.add(btn2);
      con.add(lbl3);
      con.add(txt3);
      con.add(btn3);

      }

      public void actionPerformed(ActionEvent e){
      try{
      Object sc = e.getSource();

      String a = txt1.getText();
      String b = txt2.getText();

      if(sc==btn1){



      }
      else if(sc==btn2){

      }
      else if(sc==btn3){
      System.exit(0);
      }
      }
      catch(NumberFormatException error){
      JOptionPane.showMessageDialog(null, "Error");

      }
      }
      public static void main(String[]args){

      Distruc dt = new Distruc();

      dt.setSize(170,240);
      dt.setVisible(true);
      dt.setResizable(false);
      dt.setTitle("Distruc");
      dt.setLocationRelativeTo(null);
      dt.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
      }
      }

      pls help...

      Delete
  4. plz tell me gcd program via factorial

    ReplyDelete
  5. plz help me with this....Wap in Java to input two numbers in LCM and GCM make use of the function
    1.void take(int a,int b)-to take the value of a and b.
    2.void calculate-calculate GCD and LCM.
    3.void show-display output.

    ReplyDelete
  6. Please help with recursive method for lcm

    ReplyDelete
  7. nice...thnx...i think it gave me only one error where i had to import scanner separately...

    ReplyDelete
  8. Can you show the code without a recursion method

    ReplyDelete
  9. The flowchart is wrong. After x=y then x%y = 0 always. Your program is simultaneously resetting x and y with the same original x and y for each reset.

    ReplyDelete
  10. logic above takes n1 > n2, so n1 & n2 should be swapped if n1 < n2

    ReplyDelete
  11. This code is super cool!!

    Can anyone do this with array of integers that the user can give inputs at the console?

    ReplyDelete
  12. String Anagram
    ==================
    Write a program to check if two given String is Anagram of each other. Your function should return true if two Strings are Anagram, false otherwise. A string is said to be an anagram if it contains same characters and same length but in different order e.g. army and Mary are anagrams. You can ignore cases for this problem but you should clarify that from your interview.

    ReplyDelete
  13. It uses recursion which will cause stackoverflow if the numbers are very large, so an iterative approach is better

    ReplyDelete
  14. Program for String anagram
    ==========================

    import java .util.*;
    class str_ana
    {
    static void main()
    {
    Scanner sc= new Scanner (System.in);
    System.out.println("Enter 2 Strings to be checked");
    String wd1 = sc.nextLine();
    String wd2 = sc.nextLine();
    wd1 = wd1.trim(); //removing extra spaces
    wd2 = wd2.trim(); //removing extra spaces
    int l1=wd1.length();
    int l2= wd2.length();
    if(l1!=l2) //checking whether the length is equal
    {
    System.out.println("not anagram");
    }
    else
    {
    char a[] = new char[l1];//initiallising array to check anagram
    char b[] = new char[l1];//l1 can be used as both their lengths are same
    int i,j,f=0;
    for( i=0; i<l1;i++)
    {
    a[i] = wd1.charAt(i);//initiallising characters of words for both arrays
    b[i] = wd2.charAt(i);
    }
    for(i=0;i<l1;i++) //this loop is used to give null value for the characters that are equal
    {
    for(j=0;j<l1;j++)
    {
    char ch = b[i];
    if (ch ==(a[j]))// checking for equality
    {
    b[i]= ' ';
    continue;
    }
    }
    }
    for(i=0; i<l1;i++)//loop for checking whether all characters are replaced by null value(here space)
    {
    if (b[i] != ' ')
    {
    f =1;
    }
    }
    if(f==1)
    System.out.println("Not an anagram");
    else
    System.out.println("Anagram");
    }
    }
    }

    ReplyDelete
  15. create a class rational which represents rational number by two double values numerator and denominator. include default and parametrized constructor. create a method to check if rational number is terminating or not. if we got remainder as zero then the rational number is called termination rational number otherwise non-terminating. also create a method to compare two rational number which accept one argument of rational type and will return true/false if the passed argument is larger/smaller.WAP in java??

    ReplyDelete
  16. plz help me 2 find gcd of 2 user entered numbers using repeated division methid.

    ReplyDelete
  17. I'm looking to find the gcd for 3 values and not two. Any comments?

    ReplyDelete
  18. public static void greatestCommonDivisor(float num,float num2){
    float i = Math.max(num, num2);
    while ((num2 / i) % 1 != 0 || (num / i) % 1 != 0){
    i --;
    }
    System.out.printf("your Greatest Common Divisor(GCD) is: %.0f",i);
    }

    ReplyDelete
  19. Can anyone say java or python is best to crack product based company

    ReplyDelete
  20. how can i reduce 6/3 with pgdc ?

    ReplyDelete

Feel free to comment, ask questions if you have any doubt.