# Python Program - Find HCF of Two Numbers

**HCF** stands for **Highest Common Factor**. The HCF of two numbers is the largest number that divides both of them.

For example - HCF of 20 and 25 is 5, and HCF of 50 and 100 is 50.

### Method 1: Using For Loop to find HCF of two numbers

In the below example, for loop is used to iterate the variable *i* from 0 to the smaller number. If both numbers are divisible by *i*, then it modifies the HCF and finally gives the HCF of two numbers.

x = 50 y = 100 if x > y: x, y = y, x for i in range(1,x+1): if x%i == 0 and y%i == 0: hcf = i print("HCF of", x, "and", y, "is:", hcf)

The above code will give the following output:

HCF of 50 and 100 is: 50

### Method 2: Using While Loop to find HCF of two numbers

In the below example, larger number is replaced by a number which is calculated by subtracting the smaller number from the larger number. The process is continued until the two numbers become equal which will be HCF of two numbers.

p = x = 20 q = y = 25 while x != y: if x > y: x = x - y else: y = y - x print("HCF of", p, "and", q, "is:", x)

The above code will give the following output:

HCF of 20 and 25 is: 5

### Method 3: Using the recursive function to find HCF of two numbers

In the below example, recursive function is used. In this method, instead of using subtraction operator(as in above example), modulus operator is used. This method is also known as **Euclidean algorithm**.

def hcf(x, y): if y == 0: return x return hcf(y, x%y) x = 250 y = 475 print("HCF of", x, "and", y, "is:", hcf(x,y))

The above code will give the following output:

HCF of 250 and 475 is: 25

### Method 4: Using gcd function of math module

The HCF of two numbers can be calculated using gcd function of math module. Consider the following example.

import math as ma x = 80 y = 100 print("HCF of", x, "and", y, "is:", ma.gcd(x,y))

The above code will give the following output:

HCF of 80 and 100 is: 20

### Recommended Pages

- Python Program - To Check Prime Number
- Python Program - Bubble Sort
- Python Program - Selection Sort
- Python Program - Maximum Subarray Sum
- Python Program - Reverse digits of a given Integer
- Python Program - Merge Sort
- Python Program - Shell Sort
- Stack in Python
- Queue in Python
- Python Program - Find LCM of Two Numbers
- Python Program - To Check Whether a Number is Palindrome or Not
- Python Program - To Check Whether a String is Palindrome or Not
- Python Program - Heap Sort
- Python Program - Quick Sort
- Python - Swap Two Numbers without using Temporary Variable
- Python Program - To Check Armstrong Number
- Python Program - Counting Sort
- Python Program - Radix Sort
- Python Program - Find Largest Number among Three Numbers
- Python Program - Print Floyd's Triangle