# 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.

Problem Description

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

Problem Solution

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.

Method 1: GCD Program in Python using Fraction Module

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

Program/Source Code

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))```
Program Explanation

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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
Runtime Test Cases

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```

Method 2: GCD Program in Python using Recursion

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

Program/Source Code

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)```
Program Explanation

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.

Runtime Test Cases

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”.

If you find any mistake above, kindly email to [email protected]