How to Find GCD of Two Numbers in Python?

📜Introduction

The mathematical term GCD (Greatest Common Divisor) describes finding the biggest common factor between two values. The greatest positive integer that divides two or more numbers that are not all zeros is called the GCD. H.C.F. is another name for GCD (Highest Common factor).

Example: There are two numbers, 5 and 10. What is the GCD/HCF of 5 and 10?

As we discuss the definition of GCD, it tells us the highest common factor or greatest common divisor that divides two numbers. In the case of 5 and 10, the highest common factor is 5.

We will be discussing the various methods to find the GCD of two numbers in python by using:

💡gcd() function

💡recursion

💡loops

💡Euclidean Algorithm

Must Recommended Topic, Floor Division in Python, Swapcase in Python

🤔Find GCD of Two Numbers in Python Using gcd() Function.

We can find GCD of two numbers in Python in several ways. Utilizing the math module's gcd() function is one of the techniques.

While using the gcd() function to find the gcd of two numbers in python, the math module must be imported. The math module will raise an import error if it is not imported.

📚Syntax

math.gcd(x, y)

Parameters

x: Non-negative integer passed as a first argument.

y: Non-negative integer passed as a second argument.

Return Type

The math will return the GCD of x and y, the highest common factor.

🧑‍💻Code

#The math module contains the gcd function
import math


#Calculating the gcd of 2 numbers.
x = 10
y = 5
hcf = math.gcd(x,y)


print(f"The computed GCD of {x} and {y} is {hcf}.")

You can also try this code with Online Python Compiler

Run Code

Output

🤔Find GCD Of Two Numbers In Python Using Recursion

Recursion is a memory-intensive Python function that uses self-referential expression to call itself. To return the number's greatest common divisor, the function will keep calling and repeating itself until the predetermined condition is satisfied.

📚Algorithm

Step 1: Take two user inputs, x and y.

Step 2: Pass the inputs as arguments to the recursive function.

Step 3: If the second number equals zero, it returns the first number.

Step 4: Else, recursively call the function with the second parameter as an argument until it gets the remainder, which divides the second parameter by the first.

🧑‍💻Code

# The math module contains the gcd function
import math


#Calculating the gcd of 2 numbers.
def gcd(x,y):
    if y == 0:
        return x
    else:
        return gcd(y,x%y)
        
x=10
y=18
print(f"The computed GCD of {x} and {y} is {gcd(100,3)}."

You can also try this code with Online Python Compiler

Run Code

Output

🤔Find GCD Of Two Numbers In Python Using Loops

🧑‍💻Code

# The math module contains the gcd function
import math


#Calculating the gcd of 2 numbers.
x = 86
y = 44
n = min(x,y)


gcd = 0
for i in range(1,n+1):
    if x%i == 0 and y%i == 0:
        gcd = i
        
print(f"The computed GCD of {x} and {y} is {gcd}.")

You can also try this code with Online Python Compiler

Run Code

Output

Because the H.C.F. (highest common factor) of two numbers always lies between 1 and the minimum, the variable n saves the minimum value of x and y. Due to the for loop's exclusive use of n+1, it will execute for n+1 times. Verify that both values may be divided by the current value at each step.  If the current value of the for loop divides both values, the current value of the for loop will be hcf. The H.C.F. (highest common factor) of x and y will be returned after completing the loop successfully.

You can try it on online python compiler.