Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
General Method for Finding the GCD
2.1.
Java
3.
Euclidean Algorithm for GCD: Repeated Subtraction
3.1.
Java
4.
Euclidean Algorithm for GCD: Repeated Division
4.1.
Java
5.
Frequently Asked Questions
5.1.
Why is the Euclidean algorithm considered efficient for finding GCD?
5.2.
Can the Euclidean algorithm be used for more than two numbers?
5.3.
What happens if one of the numbers in the GCD calculation is zero?
6.
Conclusion
Last Updated: May 8, 2024
Easy

Java Program to Compute GCD

Author Pallavi singh
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

The greatest common divisor (GCD) is an important concept in mathematics & computer science. It represents the largest positive integer that divides two or more numbers without leaving a remainder. In Java, finding the GCD of two or more numbers is a common problem that can be solved using different approaches. 

Java Program to Compute GCD

In this article, we will learn various methods to calculate the GCD in Java, including the general method, the Euclidean algorithm using repeated subtraction, & the Euclidean algorithm using repeated division. 

General Method for Finding the GCD

The general method to find the greatest common divisor (GCD) of two integers involves comparing all possible divisors of both numbers and picking the largest one that divides both without leaving a remainder. This approach, while straightforward, is not the most efficient for larger numbers but serves well for understanding the basic concept.

Let's look at an example in Java. Suppose we want to find the GCD of two numbers, 48 and 18. We would start by finding all divisors of 48 (1, 2, 3, 4, 6, 8, 12, 16, 24, 48) and 18 (1, 2, 3, 6, 9, 18). The common divisors are 1, 2, 3, and 6. Out of these, the largest is 6, which is the GCD of 48 and 18.

Here is a simple Java program that implements this method:

  • Java

Java

public class GCD {

   public static int findGCD(int number1, int number2) {

       int gcd = 1; // start with the smallest possible GCD

       for (int i = 1; i <= number1 && i <= number2; i++) {

           // check if i is a divisor of both numbers

           if (number1 % i == 0 & number2 % i == 0) {

               gcd = i; // update gcd to the current divisor if it's larger than the current gcd

           }

       }

       return gcd;

   }

   public static void main(String[] args) {

       int num1 = 48, num2 = 18;

       System.out.println("The GCD of " + num1 + " & " + num2 + " is " + findGCD(num1, num2));

   }

}

Output

The GCD of 48 & 18 is 6


In this code, we loop through all possible divisors starting from 1 up to the smallest of the two numbers. For each divisor, we check if it divides both numbers without leaving a remainder. If it does, we update the gcd variable.

Note -: This method ensures that we thoroughly check each possibility, but it can be slow if the numbers are large because it checks every number up to the minimum of the two given numbers.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Euclidean Algorithm for GCD: Repeated Subtraction

The Euclidean algorithm is a more efficient method for finding the greatest common divisor (GCD) of two numbers compared to the general method. This algorithm is based on the principle that the GCD of two numbers also divides their difference. The method using repeated subtraction repeatedly subtracts the smaller number from the larger one until the two numbers become equal. This equal number at the end is the GCD.

To understand this better, let's go through the process with an example using the numbers 48 and 18:

  1. Subtract the smaller number (18) from the larger number (48) to get a new pair of numbers: 30 and 18.
     
  2. Repeat the process: subtract 18 from 30 to get 12 and 18.
     
  3. Continue subtracting the smaller from the larger: now subtract 12 from 18 to get 6 and 12.
     
  4. Subtract 6 from 12 to get 6 and 6.
     
  5. The numbers are now the same, and we cannot subtract further. Both numbers are 6, which is the GCD.
     

Here's how you can implement this using Java:

  • Java

Java

public class EuclideanSubtraction {

   public static int gcdBySubtraction(int a, int b) {

       while (a != b) {

           if (a > b) {

               a -= b; // subtract b from a

           } else {

               b -= a; // subtract a from b

           }

       }

       return a; // or b, since a and b are equal here

   }

   public static void main(String[] args) {

       int num1 = 48, num2 = 18;

       System.out.println("The GCD of " + num1 + " & " + num2 + " is " + gcdBySubtraction(num1, num2));

   }

}

Output

The GCD of 48 & 18 is 6


In this Java program, we use a while loop to perform the subtraction repeatedly until the two numbers are equal. This condition (while (a != b)) keeps the loop running until we find the GCD. The method is more efficient than checking every possible divisor because it reduces the problem size more quickly.

Note -: This approach is particularly effective for numbers that are not too far apart in size or when one number is not much larger than the other.

Euclidean Algorithm for GCD: Repeated Division

The repeated division version of the Euclidean algorithm is an optimization over the subtraction method and is generally faster, especially for larger numbers. This method reduces the larger number by finding the remainder when the larger number is divided by the smaller one. This process repeats until the remainder is zero. The non-zero remainder just before the zero remainder is the greatest common divisor (GCD).

Here’s how it works step-by-step, using the same example numbers, 48 and 18:

  1. Divide the larger number (48) by the smaller number (18) and take the remainder: 48 divided by 18 is 2 with a remainder of 12.
     
  2. Now, use 18 as the larger number and 12 as the smaller number and repeat: 18 divided by 12 is 1 with a remainder of 6.
     
  3. Continue with 12 and 6: 12 divided by 6 is 2 with a remainder of 0.
     
  4. Since the remainder is now 0, the last non-zero remainder (6) is the GCD.
     

The Java implementation of this method is shown below:

  • Java

Java

public class EuclideanDivision {

   public static int gcdByDivision(int a, int b) {

       while (b != 0) {

           int temp = b; // temporarily store the value of b

           b = a % b; // replace b with the remainder of a divided by b

           a = temp; // replace a with the old value of b

       }

       return a; // when b is 0, a is the GCD

   }

   public static void main(String[] args) {

       int num1 = 48, num2 = 18;

       System.out.println("The GCD of " + num1 + " & " + num2 + " is " + gcdByDivision(num1, num2));

   }

}

Output

The GCD of 48 & 18 is 6


In this program, we use a while loop that runs until the second number (b) becomes zero. The key operation inside the loop is the modulus operation (a % b), which gives the remainder when a is divided by b. Each iteration updates a and b to the previous values of b and the remainder, respectively. This method efficiently narrows down the possible values for the GCD by using division, which typically reduces the problem size more significantly with each step compared to subtraction.

Note -: This variation of the Euclidean algorithm is widely used due to its efficiency and simplicity. It’s particularly useful in programming and computational applications where minimizing computation time is crucial.

Frequently Asked Questions

Why is the Euclidean algorithm considered efficient for finding GCD?

The Euclidean algorithm reduces the problem size significantly with each step, whether by subtraction or division, allowing it to quickly find the GCD even for large numbers. This efficiency is crucial in computational mathematics and programming.

Can the Euclidean algorithm be used for more than two numbers?

Yes, to find the GCD of more than two numbers, you can apply the Euclidean algorithm iteratively. Start with two numbers, find their GCD, and then use that GCD with the next number. Repeat this process until all numbers are included.

What happens if one of the numbers in the GCD calculation is zero?

If one of the numbers is zero and the other is a non-zero integer, the GCD is the non-zero number. This is because any number divided by zero is undefined, but every number is a divisor of zero.

Conclusion

In this article, we have learned about the greatest common divisor (GCD) and its importance in mathematical computations and programming. We started with a general method of finding the GCD through exhaustive divisor checks, then moved to more efficient techniques using the Euclidean algorithm, first with repeated subtraction and then with repeated division. Each method was illustrated with Java code examples, demonstrating their practical implementation. 

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry.

Previous article
JVM (Java Virtual Machine) and its Architecture
Next article
Structure of Java Program
Live masterclass