Python Program to Find GCD of Two Numbers

You can find the gcd of two numbers in Python using the Euclidean algorithm with def gcd(a, b): while b != 0: a, b = b, a % b return a.

Examples

Input48, 18

Output6

Input100, 25

Output25

Input7, 3

Output1

How to Think About It

To find the gcd of two numbers, repeatedly replace the larger number by the remainder of dividing the larger by the smaller until the remainder is zero. The last non-zero remainder is the gcd.

Algorithm

1

Get two numbers as input.

2

While the second number is not zero, do:

3

Replace the first number with the second number.

4

Replace the second number with the remainder of the first number divided by the second number.

5

When the second number becomes zero, return the first number as the gcd.

Code

python

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(gcd(48, 18))

Output

6

Dry Run

Let's trace gcd(48, 18) through the code

1

Initial values

a = 48, b = 18

2

First iteration

a, b = 18, 48 % 18 = 18, 12

3

Second iteration

a, b = 12, 18 % 12 = 12, 6

4

Third iteration

a, b = 6, 12 % 6 = 6, 0

5

End loop

b is 0, return a = 6

a	b
48	18
18	12
12	6
6	0

Why This Works

Step 1: Use the Euclidean algorithm

The Euclidean algorithm finds gcd by repeatedly replacing the larger number with the remainder of dividing it by the smaller number.

Step 2: Loop until remainder is zero

We keep updating the two numbers until the second number becomes zero, which means the first number is the gcd.

Step 3: Return the gcd

When the loop ends, the first number holds the greatest common divisor of the original two numbers.

Alternative Approaches

Using math.gcd function

python

import math
print(math.gcd(48, 18))

This is the simplest and fastest way using Python's built-in library, but it requires Python 3.5+.

Recursive Euclidean algorithm

python

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

print(gcd(48, 18))

This uses recursion instead of a loop, which is elegant but can hit recursion limits for very large inputs.

Complexity: O(log(min(a, b))) time, O(1) space

Time Complexity

The Euclidean algorithm runs in logarithmic time relative to the smaller input number because each step reduces the problem size significantly.

Space Complexity

The iterative approach uses constant extra space, only storing a few variables.

Which Approach is Fastest?

Using Python's built-in math.gcd is fastest and most optimized, while recursive and iterative implementations have similar time complexity but differ in readability and stack usage.

Approach	Time	Space	Best For
Iterative Euclidean	O(log(min(a,b)))	O(1)	General use, efficient
Recursive Euclidean	O(log(min(a,b)))	O(log(min(a,b)))	Elegant code, small inputs
math.gcd built-in	O(log(min(a,b)))	O(1)	Fastest, simplest, recommended