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), or Highest Common Divisor (HCD), or 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 both 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 have to pass at least one non-zero value.

Java Program to find 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);
	}
}

Java Program to find 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

 Please Enter the First Integer Value : 80
 Please Enter the Second Integer Value : 120

 GCD  =  40

Java Program to find 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 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;
	}
}

 Please Enter the First Integer Value : 75
 Please Enter the Second Integer Value : 1575

 GCD of 75 and 1575  =  75

Java Program to find GCD of Two Numbers Using Recursive Functions

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

 Please Enter the First Integer Value : 75
 Please Enter the Second Integer Value : 255

 GCD of 75 and 255  =  15