Java Program to find GCD of Two Numbers

Write a Java Program to find the GCD of Two Numbers using 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.

NOTE: To find the Greatest Common Divisor, we must pass at least one non-zero value.

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) or GCD of those two values using For Loop.

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:

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

First Iteration: i = 3

if(12 % 3 == 0 && 8 % 3 == 0) is False.

First Iteration: i = 1

if(12 % 4 == 0 && 8 % 4 == 0) is True. So, GCD = 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 are using the While Loop and a temporary variable to calculate the GCD of two numbers.

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

GCD of Two Numbers without using Temp

This program calculates the gcd of two numbers or the Greatest Common Measure without using any temporary variable.

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  =  9

Java 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. It helps you to debug the code very effectively.

// Java Program to find HCF of Two Numbers
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;
	}
}

Java 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.

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);
		}
	}
}

Recursive function to find the GCD of two numbers.