Java Program to Find GCD or HCF of Two Numbers - The Coding Shala

Home >> Java Programs >> Find GCD of Two Numbers

 Hey there, welcome back to another post. In this post, we will learn how to find GCD or HCF of Two Numbers in Java.

Java Program to Find GCD or HCF of Two Numbers

The GCD (Greatest Common Divisor) or HCF (Highest Common Factor) of two numbers is the largest number that divides both of them. For example: 

Number1: 6 (2 * 3)
Number2: 9 (3 * 3)
GCD or HCF of 6 and 9 is: 3

Find GCD of Two Numbers in Java using for Loop

As we already know, GCD is the largest number that divides both numbers. We can start a for loop from 1 (because 1 divides all the numbers) to both numbers and if it divides both numbers then update GCD.

Java Program: 

import java.util.Scanner;

/**
 * https://www.thecodingshala.com/
 */

public class Main {

    public static void findGCD(int num1, int num2) {
        int gcd = 1;
        if (num1 == 0) {
            gcd = num2;
        }
        if (num2 == 0) {
            gcd = num1;
        }

        // find largest common divisor
        for (int i = 1; i <= num1 && i <= num2; i++) {
            if (num1%i == 0 && num2%i == 0) {
                gcd = i;
            }
        }

        System.out.println(gcd);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter first number");
        int num1 = sc.nextInt();
        System.out.println("Enter second number");
        int num2 = sc.nextInt();

        System.out.println("GCD of " + num1 + " and " + num2 + " is:");
        findGCD(num1, num2);
    }
}

Output: 

Enter first number
36
Enter second number
60
GCD of 36 and 60 is:
12

Fing GCD of Two Numbers in Java using While Loop

We can find the HCF or GCD of two numbers using a while loop.

Java Program: 

import java.util.Scanner;

/**
 * https://www.thecodingshala.com/
 */

public class Main {

    public static void findGCD(int num1, int num2) {
        if (num1 == 0) {
            System.out.println(num2);
            return;
        }

        if (num2 == 0) {
            System.out.println(num1);
            return;
        }

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

        System.out.println(num1);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter first number");
        int num1 = sc.nextInt();
        System.out.println("Enter second number");
        int num2 = sc.nextInt();

        System.out.println("GCD of " + num1 + " and " + num2 + " is:");
        findGCD(num1, num2);
    }
}

Output: 

Enter first number
36
Enter second number
60
GCD of 36 and 60 is:
12

Other Posts You May Like

• Java Program to Calculate the Power of a Number
• Java Program to Find Factorial of a Number
• Java Program to Find Fibonacci Series
• Java Program to Print Pascals's Triangle
• Java Program to Check Armstrong Number

Please leave a comment below if you like this post or found some errors, it will help me to improve my content.