Simple Java program to find GCD (Greatest Common Divisor) or GCF (Greatest Common Factor) or HCF (Highest common factor). The GCD of two numbers is the largest positive integer that divides both the numbers fully i.e. without any remainder. There are multiple methods to find GCD, GDF, or HCF of two numbers but Euclid's algorithm is very popular and easy to understand, of course, only if you understand how recursion works. Euclid's algorithm is an efficient way to find the GCD of two numbers and it's pretty easy to implement using recursion in the Java program. According to Euclid's method GCD of two numbers, a, b is equal to GCD(b, a mod b) and GCD(a, 0) = a. The latter case is the base case of our Java program to find the GCD of two numbers using recursion. You can also calculate the greatest common divisor in Java without using recursion but that would not be as easy as the recursive version, but still a good exercise from the coding interview point of view. It's very easy to understand this algorithm once you look at the flow chart, which explains how Euclid's GCD algorithm works. You can also read Introduction to Algorithms by Thomas Cormen to learn more about similar computer algorithms. This is one of the most popular books to learn Data structure and algorithms and widely used as textbooks for algorithms in many schools, colleges, and universities. It is also popularly known as CLRS (Cormen, Leiserson, Rivest, Stein).
GCD [Greatest Common Divisor] of Two Integers in Java
In Euclid's algorithm, we start with two numbers X and Y. If Y is zero then the greatest common divisor of both will be X, but if Y is not zero then we assign the Y to X and Y becomes X%Y. Once again we check if Y is zero, if yes then we have our greatest common divisor or GCD otherwise we keep continue like this until Y becomes zero.
Since we are using the modulo operator, the number is getting smaller and smaller at each iteration, so the X%Y will eventually become zero.
Let' take an example of calculating GCD of 54 and 24 using Euclid's algorithm. Here X = 54 and Y = 24 since Y is not zero we move to the logical part and assign X = Y, which means X becomes 24 and Y becomes 54%24 i.e 6.
Since Y is still not zero, we again apply the logic. This time X will become 6 and Y will become 24%6 i.e. Y=0. Bingo, Y is now zero which means we have our answer and it's nothing but the value of X which is 6 (six).
The algorithm will become clearer when you see the flow chart of calculating the GCD of two numbers using recursion as shown below. You can see we are starting with two numbers X and Y and if Y=0 then we got our answer, otherwise, we apply logic and check again.
Now let's learn how to convert Euclid's algorithm to find GCD into Java code.
Here is my complete code example of how to find the GCD of two numbers in Java. This Java program uses Euclid's method to find the GCD of two numbers. They must be an integer, so make sure you check the numbers entered by the user like floating-point numbers are not allowed.
Similarly, any alphabets and other characters are not allowed except the '+' and '-' sign, and all these rules are ensured by Scanner.nextInt() call. This method will throw an error if the user will enter an invalid value instead of an integer.
Java Program to calculate GCD of two numbers
/**
* Java program to demonstrate How to find Greatest Common Divisor or GCD of
* two numbers using Euclid’s method. There are other methods as well to
* find GCD of two number in Java but this example of finding GCD of two number
* is most simple.
*
* @author Javin Paul
*/
public class GCDExample {
public static void main(String args[]){
//Enter two number whose GCD needs to be calculated.
Scanner scanner = new Scanner(System.in);
System.out.println("Please enter first number to find GCD");
int number1 = scanner.nextInt();
System.out.println("Please enter second number to find GCD");
int number2 = scanner.nextInt();
System.out.println("GCD of two numbers " + number1 +" and "+
number2 +" is :" + findGCD(number1,number2));
}
/*
* Java method to find GCD of two number using Euclid's method
* @return GDC of two numbers in Java
*/
private static int findGCD(int number1, int number2) {
//base case
if(number2 == 0){
return number1;
}
return findGCD(number2, number1%number2);
}
} Output:
Please enter first number to find GCD
54
Please enter second number to find GCD
24
GCD of two numbers 54 and 24 is :6That’s all on how to find the GCD of two numbers in Java. You can use this Java program to prepare for viva or other computer homework and assignment test or for your self-practice to improve programming in Java. BTW, there is a couple of other techniques to find Greatest common divisor in Java, as an exercise you can explore those methods and write code for that. The key point is you need to learn how to convert an algorithm into code to become a programmer.
Source: Java67
The Tech Platform
Comments