Java Program to find GCD of Two Numbers

Write a Java Program to find GCD of Two Numbers using For Loop, While Loop, and recursive method. The Greatest Common Divisor (GCD) 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, GCD of two or more integers is the largest positive integer that divides the given integer without any remainder. For example, Java 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 or GCD in Java, we have to pass at least one non-zero value.

Java Program to find GCD of Two Numbers using For Loop

This program for gcd of two numbers in java 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.

// Java Program to find GCD of Two Numbers
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 1

Java Program to find GCD of Two Numbers using While Loop

In this gcd of two numbers program, we are using the While Loop and a temporary variable to calculate the GCD.

// Java Program to find GCD of Two Numbers
import java.util.Scanner;

public class GCDofTwo2 {
	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);
	}
}

Java GCD of Two Numbers 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 Java program to calculate gcd of two numbers calculate the Greatest Common Measure without using any temporary variable.

// Java Program to find GCD of Two Numbers
import java.util.Scanner;

public class GCDofTwo3 {
	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);
	}
}

Java GCD using temp value output

 Please Enter the First Integer Value : 27
 Please Enter the Second Integer Value : 360

 GCD  =  9

Program to find GCD of Two Numbers using Method

This program to find gcd of two numbers is the same as the above example. However, this time we separated the Java logic 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 GCDofTwo4 {
	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 GCD of Two Numbers using functions

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

 GCD of 75 and 1575  =  75

Java Program to Calculate GCD of Two Numbers using Recursive Method

This Java program to calculate gcd of two numbers calculate the Greatest Common Divisor by calling HCFofTwo function recursively. I mean, recursive function calling.

// Java Program to find HCF of Two Numbers
import java.util.Scanner;

public class GCDofTwo5 {
	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);
		}
	}
}

Java recursive function to find GCD

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

 GCD of 75 and 255  =  15