Python Program to Calculate the HCF/GCD

Have you mastered basic programming topics of java and looking forward to mastering advanced topics in a java programming language? Go with these ultimate Advanced java programs examples with output & achieve your goal in improving java coding skills.

Highest Common Factor (HCF) / Greatest Common Divisor (GCD) :

When at least one of the integers is not zero, the greatest positive integer that evenly divides the numbers without a remainder is called the Highest Common Factor or Greatest Common Divisor.

The GCD of 12 and 16 is, for example, 4.

Given two numbers the task is to find the highest common factor of the two numbers in Python.

Examples:

Example1:

Input:

a= 24   b=36

Output:

The Highest Common Factor (HCF) of the numbers 24 36 = 12

Example2:

Input:

a= 18 b=72

Output:

The Highest Common Factor (HCF) of the numbers 18 72 = 18

Example3:

Input:

a= 4 b=8

Output:

The Highest Common Factor (HCF) of the numbers 4 8 = 4

Example4:

Input:

a= 9 b=9

Output:

The Highest Common Factor (HCF) of the numbers 9 9 = 9

Explanation:

 The Highest common factor of two numbers is number itself if both the numbers are equal

Python Program to Calculate the HCF/GCD

There are several ways to calculate the hcf of the two numbers in python some of them are:

Using loops
Using Euclidean algorithm
Using gcd() function in math module

Explore more instances related to python concepts from Python Programming Examples Guide and get promoted from beginner to professional programmer level in Python Programming Language.

Method #1:Using loops

Below is the implementation:

# function which computes and returns the highest common factor of the given two numbers
def findGcd(number1, number2):

    # finding the smaller number
    if number1 > number2:
        smallNumber = number2
    else:
        smallNumber = number1
    # using for loop to traverse from 1 to smaller number
    for i in range(1, smallNumber+1):
      # if it divides the given two numbers without leaving the
      # remainder then assign result it with that loop iterator value
        if((number1 % i == 0) and (number2 % i == 0)):
            result = i
    # return the final result which is greatest common divisor(GCD)
    return result


# given two numbers
# given number a
number1 = 24
# given number b
number2 = 36
# passing the given two numbers to findGcd function which returns the greatest common factor of the given two numbers
ans = findGcd(number1, number2)
# print the hcf of the given two numbers
print("The Highest Common Factor (HCF) of the numbers", number1, number2, "=", ans)

Output:

The Highest Common Factor (HCF) of the numbers 24 36 = 12

Explanation:

The findGcd() function is called with two integers stored in variables number1 and number2. The function computes and returns the H.C.F. of these two integers.

Because the H.C.F can only be less than or equal to the lowest number, we first find the smaller of the two integers in the function. Then, to move from 1 to that number, we utilize a for loop.

We check if our number divides both input numbers precisely in each cycle. If this is the case, the number is saved as H.C.F. We wind up with the greatest integer that divides both numbers properly at the end of the loop.

The method described above is simple to learn and apply, but it is inefficient. The Euclidean algorithm is a significantly more efficient technique of calculating the H.C.F.

Method #2:Using Euclidean algorithm

This approach is based on the fact that the H.C.F. of two numbers also divides their difference.

We divide the greater by the smaller and take the remainder in this algorithm. Divide the smaller number by the remainder. Repeat until the residual equals zero.

Facts of Euclidean Algorithm:

GCD does not change when we subtract a smaller number from a larger number (we reduce a larger number). So, if we keep subtracting the largest of two numbers, we get GCD.
Instead of subtracting, we can divide the smaller integer, and the procedure will terminate when we find a remainder of zero.

Algorithm:

Let number1 and number2 be the two numbers in the pseudocode of the algorithm.
number1 mod number2 =R
Assume that number1= number2 and number2 = R.
Continue with Steps 2 and 3 until number1 mod number2 is greater than 0.
GCD = number2
Print the GCD

Below is the implementation:

# function which computes and returns the highest common factor of the given two numbers
def findGcd(number1, number2):
    while(number2):
        number1, number2 = number2, number1 % number2
    return number1


# given two numbers
# given number a
number1 = 24
# given number b
number2 = 36
# passing the given two numbers to findGcd function which returns the greatest common factor of the given two numbers
ans = findGcd(number1, number2)
# print the hcf of the given two numbers
print("The Highest Common Factor (HCF) of the numbers", number1, number2, "=", ans)

Output:

The Highest Common Factor (HCF) of the numbers 24 36 = 12

Explanation:

We’ll keep looping until y equals zero. In Python, the statement number1, number2 = number2, number1 % number2 swaps values.

In each iteration, the value of number2 is placed in number1 and the remainder (number1 % number2) is placed in number2. We have H.C.F. in number1 when number2 becomes zero.

Method #3:Using gcd() function in math module

This is the simplest and quick method to calculate the greatest common divisor of the given two numbers.

Approach:

Import the math module
Use math.gcd(number1,number2) to calculate the gcd of the numbers number1 and number2.
Print the result.

Below is the implementation:

# importing math module
import math
# function which computes and returns the highest common factor of the given two numbers


def findGcd(number1, number2):
    # calculating gcd using gcd() function
    resGcd = math.gcd(number1, number2)
    # return the gcd of the number 1 and number2
    return resGcd


# given two numbers
# given number a
number1 = 24
# given number b
number2 = 36
# passing the given two numbers to findGcd function which returns the greatest common factor of the given two numbers
ans = findGcd(number1, number2)
# print the hcf of the given two numbers
print("The Highest Common Factor (HCF) of the numbers", number1, number2, "=", ans)

Output:

The Highest Common Factor (HCF) of the numbers 24 36 = 12

Explanation :It just calculated the gcd in 1 line which is math.gcd()
Related Programs: