# Python Program to Calculate HCF (GCD) by Euclidean Algorithm

#### This python program calculates Highest Common Factor (HCF) a.k.a. Greatest Common Divisor (GCD) of two numbers using Euclidean Algorithm.

To know more about Euclidean Algorithm to calculate HCF or GCD, see Euclidean Algorithm on Wikipedia.

Also try: Calculate HCF Online

## Python Source Code: HCF Using Euclidean Algorithom

``````
# Calculating HCF(GCD) using Euclidean ALgorithm

# Defining function to calculate HCF by Euclidean ALgorithm
def hcf(a,b):
while b:
temp = b
b = a %b
a = temp
return a

first = int(input('Enter first number: '))
second = int(input('Enter second number: '))

# Function call & displaying output HCF (GCD)
print('HCF or GCD of %d and %d is %d' %(first, second, hcf(first, second)))

``````

## HCF by Euclidean Method Python Program Output

```Enter first number: 12
Enter second number: 18
HCF or GCD of 12 and 18 is 6
```

This python program can be modified to reduce code size as follows:

## Python Source Code: HCF Using Euclidean Algorithom (Reduced Code)

``````
# Calculating HCF(GCD) using Euclidean ALgorithm

# Defining function to find HCF the Using Euclidian algorithm
def hcf(a, b):
while b:
a, b = b, a % b
return a