Python Tutorials

Python Programs

Python Find HCF or GCD

Python Find HCF or GCD

In this tutorial, we will learn how to find the Highest Common Factor (HCF) or Greatest Common Divisor (GCD) of two numbers in Python. We will cover the basic concept of HCF/GCD and implement functions to perform the calculation using both the built-in math library and a regular method.

What is HCF or GCD

The Highest Common Factor (HCF) or Greatest Common Divisor (GCD) of two or more integers is the largest positive integer that divides each of the integers without leaving a remainder. For example, the HCF/GCD of 8 and 12 is 4.

Syntax

The syntax to find the HCF or GCD of two numbers in Python can be done in two ways:

import math

def find_hcf_math(a, b):
    return math.gcd(a, b)

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

Finding the HCF or GCD of two numbers using the math library

We can use the built-in math library in Python to find the HCF or GCD of two numbers.

For example,

  1. Import the math module.
  2. Define a function named find_hcf_math that takes two parameters a and b.
  3. Use the math.gcd function to find the HCF or GCD of the two numbers.
  4. Return the result.
  5. Call the function with sample values and print the result.

Python Program

import math

def find_hcf_math(a, b):
    return math.gcd(a, b)

# Find the HCF/GCD of 8 and 12 using the math library
result = find_hcf_math(8, 12)

# Print the result
print('HCF/GCD of 8 and 12 using math library is', result)

Output

HCF/GCD of 8 and 12 using math library is 4

Finding the HCF or GCD of two numbers using a regular method

We can use the Euclidean algorithm to find the HCF or GCD of two numbers by iterating through the modulo operation.

For example,

  1. Define a function named find_hcf_regular that takes two parameters a and b.
  2. Use a while loop to iterate until b becomes zero.
  3. In each iteration, set a to b and b to a % b.
  4. Return the value of a after the loop ends.
  5. Call the function with sample values and print the result.

Python Program

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

# Find the HCF/GCD of 8 and 12 using the regular method
result = find_hcf_regular(8, 12)

# Print the result
print('HCF/GCD of 8 and 12 using regular method is', result)

Output

HCF/GCD of 8 and 12 using regular method is 4