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:

 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.