Online Ethical Hacking Course

Apply Now

Examples

Find GCD of Two Numbers in Java (HCF Program)

In computer science and mathematics, the concept of finding the Greatest Common Divisor (GCD) or Highest Common Factor (HCF) holds significant importance. Whether you are a seasoned programmer or just starting your journey in coding, understanding how to find GCD of 2 numbers in Java and its applications can prove to be a valuable asset.

In this tutorial, we will learn about the GCD program in Java or ways to find HCF in Java.

Uses of GCD:

  • Simplifying Fractions: When working with fractions, finding the GCD of the numerator and denominator allows you to simplify the fraction to its lowest terms. This not only makes mathematical expressions more manageable but also aids in solving real-world problems involving ratios and proportions.

  • Euclidean Algorithm: The Euclidean Algorithm, based on the concept of GCD, is a fundamental algorithm used to find the GCD of two numbers efficiently. It has applications in cryptography, data compression, and various areas of computer science.

  • Prime Numbers: Prime factorization, an essential concept in number theory, relies on the GCD to determine the common prime factors of two or more numbers. This is crucial in cryptography, where prime numbers play a significant role in ensuring security.

  • Modular Arithmetic: In computer science and cryptography, modular arithmetic is a vital tool. GCD helps identify numbers that are coprime (have a GCD of 1), which is essential for solving modular equations and ensuring data integrity in encryption and decryption processes.

  • Algorithm Optimization: Understanding GCD is crucial for optimizing algorithms and data structures. For instance, it's used in reducing fractions within data structures like rational numbers, which can lead to better performance in various applications.

So, let’s get started and practically learn the GCD program in Java, explore its efficiency, and see examples. 

Concepts to Learn:

Find GCD of Two Numbers in Java

Here, we will use the Euclidean Algorithm to find the GCD or HCF of two numbers in Java. The Euclidean Algorithm is one of the most efficient methods to calculate the GCD of two numbers.

Code

public class GCDExample {
    public static void main(String[] args) {
        int num1 = 48;
        int num2 = 18;
        int gcd = calculateGCD(num1, num2);
        System.out.println("GCD of " + num1 + " and " + num2 + " is " + gcd);
    }

    public static int calculateGCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

Output

GCD of 48 and 18 is 6

Explanation

In this example, we have two integers, num1 and num2, with values 48 and 18, respectively.

Here's how the algorithm works:

  • Initialize two variables, a and b, with the values of the two numbers (48 and 18 in this case).

  • Use a while loop to repeatedly calculate the remainder of a divided by b. Replace a with b, and b with the remainder.

  • Continue this process until b becomes 0.

At this point, the value of a will be the GCD of the original two numbers.

In our example, the algorithm proceeds as follows:

  • Initial: a=48, b=18

  • Iteration 1: a=18, b=12

  • Iteration 2: a=12, b=6

  • Iteration 3: a=6, b=0 (termination)

The final value of a (which is 6) is the GCD of 48 and 18. This method efficiently finds the GCD of two numbers by repeatedly applying the principle that the GCD doesn't change when you replace the larger number with its remainder when divided by the smaller number.

Full Stack Developer Course

GCD of Two Numbers in Java Using Recursion

Here, we are using the recursion to calculate GCD in Java programming:

Code

public class GCDExample {
    public static void main(String[] args) {
        int num1 = 48;
        int num2 = 18;
        int gcd = calculateGCD(num1, num2);
        System.out.println("GCD of " + num1 + " and " + num2 + " is " + gcd);
    }

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

Output

GCD of 48 and 18 is 6

Explanation

In this example, we use two integers, num1 and num2, with values 48 and 18, respectively.

Here's how the algorithm works:

  • In the calculateGCD function, we check if b is equal to 0. If it is, we return a as the GCD because any number divided by 0 is the number itself.

  • If b is not equal to 0, we call calculateGCD recursively with the arguments b and a % b. This step effectively replaces a with b and b with the remainder when a is divided by b.

  • The recursion continues until b becomes 0.

At that point, the value of a is the GCD of the original two numbers.

In our example, the recursive calls proceed as follows:

  • Initial call: calculateGCD(48, 18)

  • Recursive call: calculateGCD(18, 12)

  • Recursive call: calculateGCD(12, 6)

  • Recursive call: calculateGCD(6, 0) (termination)

At this point, the function returns 6, which is the GCD of 48 and 18, as confirmed by the output.

GCD Program in Java Using BigInteger Class

Here, will use the BigInteger Class's gcd method:

Code

import java.math.BigInteger;

public class GCDExample {
    public static void main(String[] args) {
        BigInteger num1 = new BigInteger("48");
        BigInteger num2 = new BigInteger("18");
        BigInteger gcd = num1.gcd(num2);
        
        System.out.println("GCD of " + num1 + " and " + num2 + " is " + gcd);
    }
}

Output

GCD of 48 and 18 is 6

Explanation

In this example, we calculate the GCD or HCF of two numbers, num1 and num2, using the BigInteger class's gcd method. This method is particularly useful when dealing with very large numbers that may exceed the capacity of primitive data types like int or long.

Here's how this method works:

  • We import the java.math.BigInteger class, which provides support for arbitrary-precision integers.

  • We create two BigInteger objects, num1 and num2, initialized with the values 48 and 18, respectively.

  • We use the gcd method of the BigInteger class to calculate the GCD of num1 and num2. This method automatically computes the GCD of two BigInteger objects.

The result is stored in the gcd variable, and we can easily print the GCD to the console

Learn Next: