Java Program to Find GCD of Two Numbers

The GCD (Greatest Common Divisor) of two numbers is the largest positive integer number that divides both the numbers without leaving any remainder. For example. GCD of 30 and 45 is 15. GCD also known as HCF (Highest Common Factor). In this tutorial we will write couple of different Java programs to find out the GCD of two numbers.

How to find out the GCD on paper?

To find out the GCD of two numbers we multiply the common factors as shown in the following diagram:

Example 1: Java Program to find GCD of two numbers using for loop

In this example, we are finding the GCD of two given numbers using for loop.

We are running a for loop from 1 to the smaller number and inside loop we are dividing both the numbers with the loop counter “i” which ranges from 1 to the smaller number value. If the value of i divides both numbers with no remainder then we are assigning that value to the variable “gcd”. At the end of the loop, the variable “gcd” will have the largest number that divides both the numbers without remainder.

public class GCDExample1 {

    public static void main(String[] args) {

    	//Lets take two numbers 55 and 121 and find their GCD
        int num1 = 55, num2 = 121, gcd = 1;

        /* loop is running from 1 to the smallest of both numbers
         * In this example the loop will run from 1 to 55 because 55
         * is the smaller number. All the numbers from 1 to 55 will be 
         * checked. A number that perfectly divides both numbers would
         * be stored in variable "gcd". By doing this, at the end, the 
         * variable gcd will have the largest number that divides both
         * numbers without remainder.
         */
        for(int i = 1; i <= num1 && i <= num2; i++)
        {
            if(num1%i==0 && num2%i==0)
                gcd = i;
        }

        System.out.printf("GCD of %d and %d is: %d", num1, num2, gcd);
    }

}

Output:

GCD of 55 and 121 is: 11

Example 2: Finding GCD of two numbers using while loop

Lets write the same program using while loop. Here we are taking a different approach of finding gcd. In this program we are subtracting the smaller number from the larger number until they both become same. At the end of the loop the value of the numbers would be same and that value would be the GCD of these numbers.

public class GCDExample2 {

    public static void main(String[] args) {

        int num1 = 55, num2 = 121;

        while (num1 != num2) {
        	if(num1 > num2)
                num1 = num1 - num2;
            else
                num2 = num2 - num1;
        }

        System.out.printf("GCD of given numbers is: %d", num2);
    }

}

Output:

GCD of given numbers is: 11

Example 3: Finding GCD of two input(Entered by user) numbers

In this example, we are using Scanner to get the input from user. The user would enter the value of both the numbers and program would find the GCD of these entered numbers.

import java.util.Scanner;
public class GCDExample3 {

    public static void main(String[] args) {

        int num1, num2;
        
        //Reading the input numbers
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter first number:");
        num1 = (int)scanner.nextInt();
        
        System.out.print("Enter second number:");
        num2 = (int)scanner.nextInt();
        
        //closing the scanner to avoid memory leaks
        scanner.close();
        while (num1 != num2) {
        	if(num1 > num2)
                num1 = num1 - num2;
            else
                num2 = num2 - num1;
        }

        //displaying the result
        System.out.printf("GCD of given numbers is: %d", num2);
    }

}

Output:

Enter first number:30
Enter second number:250
GCD of given numbers is: 10

Here are a few related java examples:
1. Java program to find factorial
2. Java program to display Fibonacci series
3. Java program to find the largest number among three numbers