Find HCF Of Two Numbers In Python

Last Updated on July 4, 2023 by Mayank Dham

The full form of HCF is the Highest Common Factor. The H.C.F. defines the greatest factor present in between given two or more numbers, In this article, we will look at various Python methods for calculating the HCF of two numbers.

What is HCF of two numbers in Python?

The Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD), is a basic mathematical concept that is used in a variety of applications.
Example:
Input: 54 and 72
Output: 18

We will cover multiple techniques, each with its own approach and advantages.

1. Using Euclidean Algorithm
2. Using gcd() function
3. Using prime factorization
4. Using recursive function
5. Using iteration loops

Using Euclidean Algorithm to find HCF of two numbers in Python

The Euclidean Algorithm is a popular method for calculating the HCF of two numbers.
It entails finding the remainder when dividing the larger number by the smaller number recursively until the remainder becomes zero.
The HCF of the two numbers is the last non-zero remainder.

Python Code

def euclidean_hcf(a, b):
    while b:
        a, b = b, a % b
    return a

num1 = 54
num2 = 72
hcf = euclidean_hcf(num1, num2)
print("HCF:", hcf)

Output: 18
Using math.gcd() Function to find HCF of two numbers in Python
Python includes a math module that includes the gcd() function.
We can use this function to find the HCF directly by passing the two numbers as arguments.
Python Code
import math

num1 = 54
num2 = 72
hcf = math.gcd(num1, num2)
print("HCF:", hcf)

Output:

18

Using Prime Factorization to find HCF of two numbers in Python

Prime factorization is another method for determining the HCF.
We divide both numbers into prime factors and look for common factors.
The HCF is the product of these common factors.

Python Code

def prime_factors(n):
    factors = []
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

def hcf_prime_factorization(a, b):
    factors_a = prime_factors(a)
    factors_b = prime_factors(b)
    common_factors = set(factors_a).intersection(factors_b)
    hcf = 1
    for factor in common_factors:
        hcf *= factor
    return hcf

num1 = 54
num2 = 72
hcf = hcf_prime_factorization(num1, num2)
print("HCF:", hcf)

Output:

18

Using Recursive Function to find HCF of two numbers in Python

We can write a recursive function that calls itself repeatedly.
The smaller number is passed as the first argument, and the remainder of the division is passed as the second argument.
The problem is simplified by reducing it to finding the HCF of two smaller numbers.

Python Code

def recursive_hcf(a, b):
    if b == 0:
        return a
    return recursive_hcf(b, a % b)

num1 = 54
num2 = 72
hcf = recursive_hcf(num1, num2)
print("HCF:", hcf)

Output:

18

Using Iterative Loop to find HCF of two numbers in Python

An iterative loop approach involves checking each number starting with the smaller number and working your way down until you reach 1.
The HCF is found by identifying the first number that divides both input numbers without leaving a remainder.

Python Code

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

num1 = 54
num2 = 72
hcf = iterative_hcf(num1, num2)
print("HCF:", hcf)

Output:
18

Conclusion
In this article, we looked at various Python methods for calculating the HCF of two numbers. The Euclidean Algorithm is a popular and efficient approach, while the math.gcd() function provides a convenient built-in solution. The prime factorization method provides a novel approach to determining the HCF, whereas the recursive function and iterative loop provide alternatives. Developers can select the best method for their application based on the complexity of the numbers and the specific requirements. By understanding these techniques, one can confidently use Python’s versatile capabilities to find the HCF of any two numbers.

Frequently Asked Questions (FAQs)

Q1. What is the product of two numbers’ HCF?
The largest positive integer that divides two given numbers without leaving a remainder is known as the Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD).

Q2.Can I use these methods to calculate the HCF of more than two numbers?
The methods presented in this article are designed specifically for calculating the HCF of two numbers. If you want to find the HCF of more than two numbers, you can iteratively use the HCF of the first two numbers as an input along with the next number.

Q3.What is the distinction between the Euclidean algorithm and the method of prime factorization?
The Euclidean algorithm is an efficient iterative method for determining the HCF that employs division and remainder operations. Finding the prime factors of both numbers and then identifying the common factors to calculate the HCF is the process of prime factorization.

Q4. Are these methods restricted in any way?
The methods provided can be used to calculate the HCF of any two positive integers. However, for large numbers with many prime factors, the prime factorization method may become slower.

Q5. Is it possible to use these methods to calculate the HCF of decimal or floating-point numbers?
No, these methods only work with positive integers. If you need to find the common factor or divisor of two decimal or floating-point numbers, convert them to integers by multiplying by a power of ten, and then use these methods.