Prime #### Prepinsta Prime

Video courses for company/skill based Preparation

(Check all courses)
Get Prime Video
Prime #### Prepinsta Prime

Purchase mock tests for company/skill building

(Check all mocks)
Get Prime mock

# Java Program to find GCD or HCF of two numbers

## GCD or HCF of two numbers using Java :

GCD(Greatest Common Divisor) or HCF(Highest Common Factor) of two numbers is the number which is the largest common factor of both numbers.It is also referred as Greatest Common Factor(GCF), Greatest Common Measure(GCM), Highest Common Divisor(HCD)

Or, we can say that GCD or HCF of two numbers is the largest number that divides both the numbers.For better understanding let’s consider an example : –

For example let’s consider two numbers 15 and 35, then

Factors of 15 are 1, 3, 5 and 15

Factors of 35 are 1, 5, 7 and 35

Highest Common factor of 15 and 35 is 5, which is the result of HCF.

So, now we will create a java program to calculate hcf or gcd of two numbers with the help of a loop and nested if-else statements. ### Working :

Step 1 : Ask the user to enter two numbers and store in two different variables of same Datatype with name num1 and num2.

Step 2 : Declare a third variable n for storing the divisor and store 1 in it.

(We stored 1 because we have the condition in while loop for (n != 0) and this is the very first condition to enter inside the loop at the first time)

Step 3 : Use the condition to check that the entered numbers should not be same.If this statement get true then move to the Step 4, else move to the Step 9 directly.

Step 4 : Use the loop to perform work in continuation till we do not get the desired result and use condition while(n != 0).

Step 5 : Calculate and store the remainder in n so that it can become divisor for another division.

Step 6 : Use the if statement for changing divisor and dividend.

Step 7 : Follow the step 4 to 6 till we do not get the remainder 0 and get the Highest Common Factor.

Step 8 : Print the result.

Step 9 :  Print the message i.e. “Wrong Input”.

### Code in Java :

`//Java program to find GCD or HCF of two numbersimport java.util.Scanner;public class gcd_or_hcf{	public static void main(String[] args)	{		//scanner class declaration		Scanner sc = new Scanner(System.in);		//input from the user				System.out.print("Enter the first number : ");				int num1 = sc.nextInt();		//input from the user		System.out.print("Enter the second number : ");				int num2 = sc.nextInt();		int n = 1;		System.out.print("HCF of "+num1+" and "+num2+" is ");		if( num1 != num2)		{			while(n != 0)			{				//storing remainder				n = num1 % num2;							if(n != 0)				{					num1 = num2;					num2 = n;				}			}			//result			System.out.println(num2);					}		else			System.out.println("Wrong Input");		//closing scanner class(not compulsory, but good practice)		sc.close();										}}`

### Output :

`Enter the first number : 15Enter the second number : 35HCF is = 5Enter the first number : 12Enter the second number : 12HCF is = 12` • Highest Common Factor(HCF): C | C++Java
• Lowest Common Multiple (LCM) : C | C++ | Java
• Greatest Common Divisor : C | C++ | Java
• Binary to Decimal to conversion : C | C++ | Java
• Binary to Octal conversion : C | C++ | Java
• Decimal to Binary conversion: C | C++ | Java
• Decimal to octal Conversion: C | C++ | Java
• Octal to Binary conversion : C | C++ | Java
• Octal to Decimal conversion : C | C++ | Java
• Quadrants in which a given coordinate lies : C | C++ | Java
• Permutations in which n people can occupy r seats in a classroom : C | C++ | Java
• Maximum number of handshakes: C | C++ | Java
• Addition of two fractions: C | C++ | Java
• Replace all 0’s with 1 in a given integer : C | C++ | Java
• Can a number be expressed as a sum of two prime numbers
: C | C++ | Java