Write a Java Program to find the GCD of Two Numbers using the For Loop, While Loop, and recursive method. The Greatest Common Divisor is also known as the Highest Common Factor (HCF), Highest Common Divisor (HCD), Greatest Common Factor (GCF), or Greatest Common Measure (GCM).
According to Mathematics, the GCD of two or more integers is the largest positive integer that divides the given integer without any remainder. For example, the GCD of 8 and 12 is 4 because 8 and 12 are divisible by 1, 2, and 4. The largest positive integer among the factors 1, 2, and 4 is 4.
Java Program to find the GCD of Two Numbers using For Loop
This Java program allows the user to enter two positive integer values. Next, it calculates the Highest Common Factor (HCF) of those two values using For Loop.
NOTE: To find the Greatest Common Divisor, we must pass at least one non-zero value. Refer to the For Loop in Java article.
import java.util.Scanner;
public class GCDofTwo1 {
private static Scanner sc;
public static void main(String[] args)
{
int Num1, Num2, i, GCD = 0;
sc = new Scanner(System.in);
System.out.print(" Please Enter the First Integer Value : ");
Num1 = sc.nextInt();
System.out.print(" Please Enter the Second Integer Value : ");
Num2 = sc.nextInt();
for(i = 1; i <= Num1 && i <= Num2; i++)
{
if(Num1 % i == 0 && Num2 % i == 0)
{
GCD = i;
}
}
System.out.println("\n GCD of " + Num1 + " and " + Num2 + " = " + GCD);
}
}
Analysis of the Program to find GCD of Two Numbers is.
Num1 = 12, Num2 = 8 and the for loop condition is for( i = 1; i <= 12 && i <= 8; i++).
First Iteration: i = 1
if(12 % 1 == 0 && 8 % 1 == 0) is True. So, GCD = 1
2nd Iteration: i = 2
if(12 % 2 == 0 && 8 % 2 == 0) is True. So, GCD = 2
Third Iteration: i = 3
if(12 % 3 == 0 && 8 % 3 == 0) is False.
Fourth Iteration: i = 4
if(12 % 4 == 0 && 8 % 4 == 0) is True. So, it is 4
For all the remaining iterations, the condition becomes False. So, the final output is 4.
Java Program to find the GCD of Two Numbers using While Loop
In this program, we use the While Loop and a temporary variable (temp) to calculate the GCD of two numbers. Refer to the while loop in Java article.
import java.util.Scanner;
public class GOT2 {
private static Scanner sc;
public static void main(String[] args)
{
int Num1, Num2, Temp, GCD = 0;
sc = new Scanner(System.in);
System.out.print(" Please Enter the First Integer Value : ");
Num1 = sc.nextInt();
System.out.print(" Please Enter the Second Integer Value : ");
Num2 = sc.nextInt();
while(Num2 != 0)
{
Temp = Num2;
Num2 = Num1 % Num2;
Num1 = Temp;
}
GCD = Num1;
System.out.println("\n GCD = " + GCD);
}
}
Using a While Loop output
Without using Temp
This program calculates the gcd of two numbers or the Greatest Common Measure without using any temporary variable. Refer to the Java if else.
import java.util.Scanner;
public class GOT3 {
private static Scanner sc;
public static void main(String[] args)
{
int Num1, Num2, GCD = 0;
sc = new Scanner(System.in);
System.out.print(" Please Enter the First Integer Value : ");
Num1 = sc.nextInt();
System.out.print(" Please Enter the Second Integer Value : ");
Num2 = sc.nextInt();
while(Num2 != 0)
{
if(Num1 > Num2)
{
Num1 = Num1 - Num2;
}
else
{
Num2 = Num2 - Num1;
}
}
GCD = Num1;
System.out.println("\n GCD = " + GCD);
}
}
Using temp value output.
Please Enter the First Integer Value : 27
Please Enter the Second Integer Value : 360
GCD = 9Java Program to find the GCD of Two Numbers using Functions
This program to find the gcd of two numbers is the same as the above example. However, we separated the Java logic this time and placed it in a separate method. This Java program helps you to debug the code very effectively.
import java.util.Scanner;
public class GOT4 {
private static Scanner sc;
public static void main(String[] args)
{
int Num1, Num2, GCD = 0;
sc = new Scanner(System.in);
System.out.print(" Please Enter the First Integer Value : ");
Num1 = sc.nextInt();
System.out.print(" Please Enter the Second Integer Value : ");
Num2 = sc.nextInt();
GCD = HCFofTwo(Num1, Num2);
System.out.println("\n GCD of " + Num1 + " and " + Num2 + " = " + GCD);
}
public static int HCFofTwo(int Num1, int Num2)
{
while(Num2 != 0)
{
if(Num1 > Num2)
{
Num1 = Num1 - Num2;
}
else
{
Num2 = Num2 - Num1;
}
}
return Num1;
}
}
GCD of both positive and negative numbers
In the following program, we use the Java Math.abs function to make the numbers positive. Alternatively, we can use the ternary operator to convert negative numbers to positive. This converts any negative number to positive before calculating the GCD of the two numbers. Refer to the Java ternary operator.
public class example {
public static void main(String[] args) {
int a = 12, b = -8;
a = Math.abs(a); //(a > 0) ? a : -a;
b = Math.abs(b); //(b > 0) ? b : -b;
while (a != b) {
if (a > b) {
a -= b;
} else {
b -= a;
}
}
System.out.println("GCD = " + a);
}
}
GCD = 4Java Program to find the GCD of Two Numbers Using Recursion
This program calculates the Greatest Common Divisor by calling the HCFofTwo function recursively. I mean recursive function calls. This program uses the Euclidean algorithm by division operation to calculate the GCD of two numbers.
import java.util.Scanner;
public class GOT5 {
private static Scanner sc;
public static void main(String[] args)
{
int Num1, Num2, GCD = 0;
sc = new Scanner(System.in);
System.out.print(" Please Enter the First Integer Value : ");
Num1 = sc.nextInt();
System.out.print(" Please Enter the Second Integer Value : ");
Num2 = sc.nextInt();
GCD = HCFofTwo(Num1, Num2);
System.out.println("\n GCD of " + Num1 + " and " + Num2 + " = " + GCD);
}
public static int HCFofTwo(int Num1, int Num2)
{
if(Num2 == 0)
{
return Num1;
}
else
{
return HCFofTwo(Num2, Num1 % Num2);
}
}
}
The output of the above code is.
The user entered values are: a = 75 and b = 255
Let me explain the recursive function.
HCFofTwo(75, 255) -> Since the second value is not zero, the Javac compiler calls the HCFofTwo() function recursively.
HCFofTwo(255, 75 % 255) = HCFofTwo(255, 75)
HCFofTwo(75, 255 % 75) = HCFofTwo(75, 30)
HCFofTwo(30, 75 % 30) =HCFofTwo(30, 15)
HCFofTwo(15, 30 % 15) = HCFofTwo(15, 0)
Since the second value (Num2) becomes 0, it returns 15 as the output.
Find GCD of two numbers using Euclidean algorithm by subtraction
The following program uses the Euclidean algorithm to repeatedly subtract the first number from the second to calculate the GCD of two numbers.
public class example {
public static int calculateGCD(int a, int b) {
if (b == 0)
return a;
else
return calculateGCD(b, Math.abs(a - b));
}
public static void main(String[] args) {
int a = 12, b = 8;
System.out.println("GCD = " + calculateGCD(a, b));
}
}
GCD = 4The user entered values are: a = 12 and b = 8
Let me explain the recursive function.
calculateGCD(12, 8) -> Since the second value (8) is not zero, the Javac compiler calls the calculateGCD() function recursively.
calculateGCD(8, 12 -8) = calculateGCD(8, 4). Remember, we are using the abs() function to convert the negative number (-4) to a positive (4).
calculateGCD(4, 8 – 4) = calculateGCD(4, 4)
calculateGCD(4, 4 – 4) =calculateGCD(4, 0). Since b becomes 0, the calculateGCD() function returns 4 as the output.
Also Read