GCD of Two Numbers in Python

GCD stands for Greatest Common Divisor. In Python, the GCD is a mathematical function that returns the largest positive integer that divides two or more numbers without leaving a remainder. It can be calculated using the math module or by implementing custom algorithms such as Euclidean algorithm or recursive approach.

Example: GCD(15,5) = 5, GCD(105,222) = 3.

Write a Python Program to find the GCD of two numbers.

There are multiple methods to find the GCD of two numbers in Python. Let’s explore different approaches and learn how to write a Python program to calculate the GCD of two numbers.

• GCD of Two Numbers in Python using Fraction Module
• GCD of Two Numbers in Python using Recursion

In this method, we use the fractions module in Python to calculate the greatest common divisor (GCD) of two numbers entered by the user.

Here is source code of the Python Program to find the GCD of two numbers. The program output is also shown below.

import fractions
a=int(input("Enter the first number:"))
b=int(input("Enter the second number:"))
print("The GCD of the two numbers is",fractions.gcd(a,b))

1. Import the fractions module.
2. User must enter both the numbers and store it in separate variables.
3. The in-built function of fractions.gcd(a,b) is used where a and b are the variables containing the integer values.
4. The final GCD is printed.

Time Complexity: O(1)
The time complexity of this program is constant, O(1), as it performs a fixed number of operations regardless of the input size.

Space Complexity: O(1)
The space complexity is also constant, O(1), as it only requires a small amount of additional memory to store the input values and the output.

Testcase 1: The numbers entered by the user to calculate gcd in this case are 15 and 5.

Enter the first number:15
Enter the second number:5
The GCD of the two numbers is 5

Testcase 2: The numbers entered by the user to calculate gcd are 105 and 222.

Enter the first number:105
Enter the second number:222
The GCD of the two numbers is 3

In this method, the program takes two numbers and finds the GCD of two numbers using recursion.

Here is source code of the Python Program to find the GCD of two numbers using recursion. The program output is also shown below.

def gcd(a,b):
    if(b==0):
        return a
    else:
        return gcd(b,a%b)
a=int(input("Enter first number:"))
b=int(input("Enter second number:"))
GCD=gcd(a,b)
print("GCD is: ")
print(GCD)

1. User must enter two numbers.
2. The two numbers are passed as arguments to a recursive function.
3. When the second number becomes 0, the first number is returned.
4. Else the function is recursively called with the arguments as the second number and the remainder when the first number is divided by the second number.
5. The first number is then returned which is the GCD of the two numbers.
6. The GCD is then printed.

Time Complexity: O(log(min(a, b)))
The time complexity of this program is O(log(min(a, b))), as it uses the Euclidean algorithm for finding the greatest common divisor.

Space Complexity: O(1)
The space complexity is O(1) as it does not require any additional space that grows with the input size.

Testcase 1: The numbers entered by the user to calculate gcd in this case are 5 and 15.

Enter the first number:5
Enter the second number:15
The GCD of the two numbers is 5

Testcase 2: The numbers entered by the user to calculate gcd are 30 and 12.

Enter the first number:30
Enter the second number:12
The GCD of the two numbers is 6

To practice programs on every topic in Python, please visit “Programming Examples in Python”.