 # Python Program to find the HCF or GCD

October 7, 2021, Learn eTutorial
682

In this simple python program, we need to find HCF or GCD of two numbers. It is a number python program.

To understand this example, you should have knowledge of the following Python programming topics:

## What is HCF or GCD?

In this python program, we have to find the HCF, which means Highest Common Factor. Unlike LCM, HCF is the Largest Common Divisor, wherein LCM is the Largest Common Multiple. It is straightforward. It is the highest integer, which divides both the numbers without a remainder, which means a completely divisible number.

It is also called GCD, which means the greatest common divisor. Let us take an example of two numbers 8 and 12, it has one condition that lowest not to be zero. The divisors of 8 are 1, 2, 4, `and` 8 and that of 12 are 1, 2, 3, 4, 6, 12. So in that divisors, we have to take the Highest Common one, which is 4 in this case. so the HCF or GCD(8, 12) is 4.

## How HCF or GCD calculated in Python?

Now we have to think about how this logic can be applied to our python program example. Here we have to find the smaller number and apply that number to the smaller variable using an `if` condition in python. then we have to check all divisors  x and y using a for loop starting from 1 to the smaller number. We have to find all the divisors which are divisible by both numbers using the mod operator. After the full iteration of `for loop` the largest divisor, which is divisible by both numbers will be stored in HCF.

We can understand that by taking the previous example of 8 and 12. At the start of `for loop`, for the divisor 2 all the conditions satisfied, and HCF will be 2, but the `for loop` will continue, and when the divisor 4 encountered, again all conditions satisfied, and HCF rewrites from 2 to 4 and the returning HCF will be 4. Here we are using a user-defined function to do the calculation of HCF, so we have to understand how to call a function in python.

### ALGORITHM

STEP 1: Accept both the numbers from the user using the input function in the python programming language, and store it as an integer using int().

STEP 2: Call the HCF user-defined function in python language bypassing the two numbers as parameters. Finally, print the value returning from the function as HCF.

#### User-Defined function hcf(x, y)

STEP 1: Check for the smaller value and assign it to a smaller variable.

STEP 2: Open a `for loop` from 1 to a smaller value

STEP 3: Check and find all the divisors of two numbers using the mod operator.

STEP 4: Store the value of I as HCF if both conditions got satisfied.

STEP 5: Then, HCF will be storing the largest divisor because of `for loop`.

STEP 6:  Return the value to the calling program in python Language.

## Python Source Code

```                                          ```def hcf(x, y):
if x > y:
smaller = y
else:
smaller = x
for i in range(1,smaller + 1):
if((x % i == 0) and (y % i == 0)):
hcf = i
return hcf

num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))
print("The H.C.F. or G.C.D is", hcf(num1, num2)) ```
```

## OUTPUT

```Enter first number: 8
Enter second number: 12

The H.C.F or G.C.D is 4```