Online Ethical Hacking Course

Apply Now

Examples

GCD of Three Numbers in Java (HCF of 3 Numbers Program

In mathematics and computer science, the concept of the Greatest Common Divisor (GCD) holds immense importance. The GCD of three numbers is the largest positive integer that divides each of them without leaving a remainder. It's a fundamental mathematical concept that finds application in various domains, including number theory, cryptography, and algorithm design.

In this tutorial, we will learn how to calculate the GCD of three numbers in Java programming. While there are established algorithms for finding the GCD of two numbers, extending this to three may seem like a daunting task at first glance. However, with the power of Java and some clever algorithm design, we can easily tackle this challenge.

Concepts to Learn:

Java Program for GCD of Three Numbers (Euclidean Algorithm)

The first method to find the greatest common divisor of three numbers in Java is using the Euclidean algorithm:

Code

import java.util.Scanner;

public class GCDOfThreeNumbers {
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the first number: ");
        int num1 = scanner.nextInt();
        System.out.print("Enter the second number: ");
        int num2 = scanner.nextInt();
        System.out.print("Enter the third number: ");
        int num3 = scanner.nextInt();

        int result = gcd(gcd(num1, num2), num3);

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

Output

Enter the first number: 36
Enter the second number: 48
Enter the third number: 60
The GCD of 36, 48, and 60 is: 12

Explanation

The Euclidean Algorithm is based on the principle that the GCD of two numbers remains the same as long as the smaller number is subtracted from the larger number repeatedly until one of them becomes zero.

Here's how the program works:

  • We take three integer inputs (num1, num2, and num3) from the user.

  • We calculate the GCD of num1 and num2 using the gcd method recursively. This gives us the GCD of the first two numbers.

  • We then calculate the GCD of the result obtained in step 2 and num3, again using the gcd method. This gives us the GCD of all three numbers.

  • The final GCD is displayed as the output.

Full Stack Developer Course

GCD of Three Numbers in Java Using Recursion

The second method is to find GCD or HCF of 3 numbers in Java using recursion:

Code

import java.util.Scanner;

public class GCDOfThreeNumbers {
    public static int gcd(int a, int b, int c) {
        int temp = gcd(a, b);
        return gcd(temp, c);
    }

    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the first number: ");
        int num1 = scanner.nextInt();
        System.out.print("Enter the second number: ");
        int num2 = scanner.nextInt();
        System.out.print("Enter the third number: ");
        int num3 = scanner.nextInt();

        int result = gcd(num1, num2, num3);

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

Output

Enter the first number: 36
Enter the second number: 48
Enter the third number: 60
The GCD of 36, 48, and 60 is: 12

Explanation

  • We take three integer inputs (num1, num2, and num3) from the user.

  • We have two gcd methods: one for calculating the GCD of two numbers (gcd(int a, int b)) and another for calculating the GCD of three numbers (gcd(int a, int b, int c)).

  • The gcd(int a, int b, int c) method first calculates the GCD of the first two numbers (num1 and num2) using the gcd(int a, int b) method. This gives us the GCD of the first two numbers.

  • Then, we calculate the GCD of the result obtained in step 3 and num3 using the same gcd(int a, int b) method. This gives us the GCD of all three numbers.

  • The final GCD is displayed as the output.

GCD or HCF of Three Numbers in Java Using for loop

Below is a Java program to find GCD of 3 numbers using the for loop in an interactive way:

Code

import java.util.Scanner;

public class GCDOfThreeNumbers {
    public static int gcd(int a, int b, int c) {
        int smallest = Math.min(Math.min(a, b), c);
        int gcd = 1;
        
        for (int i = 1; i <= smallest; i++) {
            if (a % i == 0 && b % i == 0 && c % i == 0) {
                gcd = i;
            }
        }
        
        return gcd;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the first number: ");
        int num1 = scanner.nextInt();
        System.out.print("Enter the second number: ");
        int num2 = scanner.nextInt();
        System.out.print("Enter the third number: ");
        int num3 = scanner.nextInt();

        int result = gcd(num1, num2, num3);

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

Output

Enter the first number: 36
Enter the second number: 48
Enter the third number: 60
The GCD of 36, 48, and 60 is: 12

Explanation

  • We take three integer inputs (num1, num2, and num3) from the user.

  • We find the smallest of the three numbers using the Math.min function. This will be used as the maximum possible value for the GCD.

  • We initialize a variable gcd to 1, which will be used to store the GCD of the three numbers.

  • We use a for loop that iterates from 1 to the smallest number. Inside the loop, we check if i is a common divisor of all three numbers (a, b, and c) by using the modulus operator (%). If it is, we update the gcd variable to the current value of i.

  • Finally, the GCD is displayed as the output.

Learn Next: