# Program to find HCF of two numbers

In this post, you will learn how to write program to find the **highest common factor (H.C.F.)** or **greatest common divisor (G.C.D)** of two numbers in different programming languages. Such a type of question is generally asked in programming interviews.

The **greatest common divisor (G.C.D)** of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers **a**, **b**, the greatest common divisor of **a** and **b** is denoted **gcd(a,b)**.

## Java program to find HCF of two numbers using for loop

Here, we define a function to compute the **G.C.D** of two numbers, **x** and **y**, and return it. In each iteration, we check if our number perfectly divides both the given numbers. If this is true, we store the number as H.C.F. At the completion of the loop, we conclude with the largest number that perfectly divides both the numbers.

```
public class GetGCD
{
public static void main(String[] args)
{
// defining variables
int x = 4, y = 10, gcd = 1;
// iterate form 1 to the smallest of both numbers
for(int i = 1; i <= x && i <= y; i++)
{
if(x%i==0 && y%i==0)
gcd = i;
}
//prints the gcd
System.out.printf("GCD of %d and %d is: %d", x, y, gcd);
}
}
```

**Output of the above code:**

`GCD of 4 and 10 is: 2`

## Java program to find HCF of two numbers using Euclidean algorithm

The **Euclidean algorithm** is an efficient way to find the greatest common divisor of two numbers, the largest number that divides them both without a remainder.

```
import java.util.Scanner;
public class ComputeGCD
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
System.out.println("Please enter the first number: ");
int x = sc.nextInt();
System.out.println("Please enter the second number: ");
int y = sc.nextInt();
System.out.println("GCD of " + x + " and " + y + " = " + findGCD(x,y));
}
static int findGCD(int x, int y)
{
int g=0, a, b;
// a is greater number
a = (x > y) ? x : y;
// b is smaller number
b = (x < y) ? x : y;
g = b;
while(a % b != 0)
{
g = a % b;
a = b;
b = g;
}
return g;
}
}
```

**Output of the above code:**

```
Please enter the first number: 15
Please enter the second number: 25
GCD of 15 and 25 = 5
```

## Python program to find HCF of two numbers using math.gcd() Method

In **Python**, the **math** module contains various mathematical functions, which can be performed effortlessly utilising the module. The **math.gcd()** method computes the greatest common divisor of two numbers.

**math.gcd(x, y)**

Here, **x** and **y** are non negative integers for computing GCD. It returns a positive integer value representing the greatest common divisor (GCD) of two integers.

```
import math
# Greatest common divisor of the two integers
print("GCD of (5, 2) = ",math.gcd(5, 2))
print("GCD of (4, 10) = ",math.gcd(4, 10))
print("GCD of (10, 0) = ",math.gcd(10, 0))
print("GCD of (-9, -16) = ",math.gcd(-9, -16))
print("GCD of (4, 14) = ",math.gcd(4, 14))
print("GCD of (6, 3) = ",math.gcd(6, 3))
```

**Output of the above code:**

```
GCD of (5, 2) = 1
GCD of (4, 10) = 2
GCD of (10, 0) = 10
GCD of (-9, -16) = 1
GCD of (4, 14) = 2
GCD of (6, 3) = 3
```

## C program to find HCF of two numbers using for loop

In the given example, we have used the C program to find the two numbers using a for loop. First, we take two numbers from the user and store them in variables **num1** and **num2**. Then, we find the minimum between the given two numbers and run the for loop from 1 to the minimum value. Inside the loop, we check if **i** is a factor of two numbers, then set **i** as HCF, i.e., **gcd = i**.

```
#include<stdio.h>
int main()
{
int num1, num2, i, gcd;
printf ( " Enter any two numbers: \n ");
scanf ( "%d %d", &num1, &num2);
for( i = 1; i <= num1 && i <= num2; ++i)
{
if (num1 % i ==0 && num2 % i == 0)
gcd = i;
}
// print the GCD of two numbers
printf (" GCD of two numbers %d and %d is %d.", num1, num2, gcd);
return 0;
}
```

**Output of the above code:**

```
Enter any two numbers:
24 42
GCD of two numbers 24 and 42 is 6.
```

## C++ program to find HCF of two numbers using while loop

In the given example, we have used the while loop to find the HCF of two numbers using **C++** programming.

```
#include <iostream>
using namespace std;
int main() {
int num1, num2;
cout << "Enter two numbers: ";
cin >> num1 >> num2;
while(num1 != num2) {
if(num1 > num2)
num1 -= num2;
else
num2 -= num1;
}
cout << "HCF = " << num1;
return 0;
}
```

**Output of the above code:**

```
Enter two numbers: 54 62
HCF = 2
```

### Related Articles

**Java program to find area of triangle**

Area of circle program in Java

Remove duplicate elements from array in Java

Capitalize first letter of each word Java

Convert binary to decimal in Java

Convert array to list Python

Python take screenshot of specific window

Web scraping Python BeautifulSoup

Check if two strings are anagrams Python

Python program to add two numbers

Print new line python

Prime factors of a number in c

Armstrong number program in c

Write a program to check leap year in c

C program to find area of rectangle

C program to convert celsius to fahrenheit

Fibonacci series program in C using recursion

Write a program to find area of circle in C

C program to convert Decimal to Octal

C program to convert decimal to binary

C program to check whether a number is even or odd

Area of circle program in Java

Remove duplicate elements from array in Java

Capitalize first letter of each word Java

Convert binary to decimal in Java

Convert array to list Python

Python take screenshot of specific window

Web scraping Python BeautifulSoup

Check if two strings are anagrams Python

Python program to add two numbers

Print new line python

Prime factors of a number in c

Armstrong number program in c

Write a program to check leap year in c

C program to find area of rectangle

C program to convert celsius to fahrenheit

Fibonacci series program in C using recursion

Write a program to find area of circle in C

C program to convert Decimal to Octal

C program to convert decimal to binary

C program to check whether a number is even or odd