Python Program to Find HCF of Two Numbers

You can find the HCF of two numbers in Python using the Euclidean algorithm with while b != 0: a, b = b, a % b and then a will be the HCF.

Examples

Inputa=12, b=15

Output3

Inputa=100, b=80

Output20

Inputa=17, b=13

Output1

How to Think About It

To find the HCF of two numbers, repeatedly replace the larger number by the remainder when the larger is divided by the smaller. When the remainder becomes zero, the smaller number at that point is the HCF. This uses the fact that the HCF does not change if the larger number is replaced by its remainder with the smaller number.

Algorithm

1

Get two numbers as input.

2

While the second number is not zero, do:

3

Replace the first number with the second number.

4

Replace the second number with the remainder of the first number divided by the second number.

5

When the second number becomes zero, return the first number as the HCF.

Code

python

def find_hcf(a, b):
    while b != 0:
        a, b = b, a % b
    return a

num1 = 12
num2 = 15
print("HCF of", num1, "and", num2, "is", find_hcf(num1, num2))

Output

HCF of 12 and 15 is 3

Dry Run

Let's trace the example where a=12 and b=15 through the code.

1

Initial values

a = 12, b = 15

2

First iteration

a, b = b, a % b → a = 15, b = 12 % 15 = 12

3

Second iteration

a, b = b, a % b → a = 12, b = 15 % 12 = 3

4

Third iteration

a, b = b, a % b → a = 3, b = 12 % 3 = 0

5

End loop

b is 0, so return a = 3

a	b
12	15
15	12
12	3
3	0

Why This Works

Step 1: Why use remainder?

The HCF of two numbers also divides their remainder, so replacing the larger number by the remainder keeps the HCF unchanged.

Step 2: Loop until remainder zero

We repeat the process until the remainder becomes zero, meaning the smaller number at that point is the HCF.

Step 3: Return the HCF

When the remainder is zero, the other number is the highest common factor of the original two numbers.

Alternative Approaches

Using math.gcd function

python

import math
num1 = 12
num2 = 15
print("HCF of", num1, "and", num2, "is", math.gcd(num1, num2))

This is the simplest and fastest way using Python's built-in function but requires importing the math module.

Using subtraction method

python

def find_hcf_sub(a, b):
    while a != b:
        if a > b:
            a -= b
        else:
            b -= a
    return a

print(find_hcf_sub(12, 15))

This method uses repeated subtraction instead of modulo but is slower for large numbers.

Complexity: O(log(min(a, b))) time, O(1) space

Time Complexity

The Euclidean algorithm runs in logarithmic time relative to the smaller input number because each step reduces the problem size significantly.

Space Complexity

The algorithm uses constant extra space since it only stores a few variables and updates them in place.

Which Approach is Fastest?

Using Python's built-in math.gcd is fastest and simplest, followed by the Euclidean algorithm with modulo. The subtraction method is slower and less efficient.

Approach	Time	Space	Best For
Euclidean algorithm (modulo)	O(log(min(a,b)))	O(1)	General use, efficient for all sizes
math.gcd function	O(log(min(a,b)))	O(1)	Quickest and simplest in Python
Subtraction method	O(min(a,b))	O(1)	Educational, but inefficient for large numbers