Tuesday, August 7, 2012

Simple Java program to find GCD (Greatest common Divisor)

How to find GCD of two numbers in Java
Simple Java program to find GCD (Greatest common Divisor) or GCF  (Greatest Common Factor) or HCF (Highest common factor). 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. Euclid's algorithm is an efficient way to find GCD of two numbers and its pretty easy to implement using recursion in 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 later case is a  based case for Java program to find GCD of two numbers using recursion


GCD of two numbers in Java Code Example:
Java program to find GCD of two numbers with Example -Euclid's method Here is complete code example of How to find GCD of two numbers in Java. This Java program uses Euclid's method to find 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 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.

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

Java67 Headline Animator